当前位置：网站首页>LeetCode 热题 HOT 100 -＞ 1.两数之和

LeetCode 热题 HOT 100 -＞ 1.两数之和

2022-07-28 00:49:00 【想进大厂的小皓同学】

题干描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
LeetCode原题链接https://leetcode.cn/problems/two-sum/

方法1：暴力枚举

方法1分析：

只要注意第二层循环要从该元素的下一个位置开始遍历即可，因为要避免同一个下标重复出现。

代码如下：

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int>ans(2);
		for (int i = 0; i < nums.size(); i++)
		{
			for (int j = i + 1; j < nums.size(); j++) //由于同一个元素不能重复出现，因此从i+1开始
			{
				if (nums[i] + nums[j] == target)
				{
					ans[0] = i;
					ans[1] = j;
				}
			}
		}
		return ans;
	}
};

复杂度分析：

时间复杂度：O（），其中是数组中的元素个数，最坏情况下数组中任意两个数都要被匹配一次。

空间复杂度：O（），仅开了常数个空间。

方法2：排序法

方法2分析：

因为是要查找两个数的和，所以很容易想到排序后使用双指针的方法来查找，问题在于题目要求返回下标，如果直接对原数组进行排序，那么就无法找到原下标了，因此我们选择开辟一个新的临时数组，再在新数组中查找，找到两个所求值之后，再在原数组中搜索下标。这里面还存在一个问题，就是原数组可能存在有重复的元素的情况，因此两个下标必须一个从前往后查找，另一个从后往前查找，这样就能避免找到同一个下标。

代码如下：

class Solution {
public:
	int FindPosFront(vector<int>& v, int val) //从前往后找
	{
		for (int i = 0; i < v.size(); i++)
		{
			if (v[i] == val)
			{
				return i;
			}
		}
		return -1;
	}
	int FindPosBack(vector<int>& v, int val) //从后往前找
	{
		for (int i = v.size() - 1; i >= 0; i--)
		{
			if (v[i] == val)
			{
				return i;
			}
		}
		return -1;
	}
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> ans(2);
		vector<int> tmp(nums);
		sort(tmp.begin(), tmp.end());
		int begin = 0;
		int end = nums.size() - 1;
		while (begin < end)
		{
			if (tmp[begin] + tmp[end] < target)
			{
				begin++;
			}
			else if (tmp[begin] + tmp[end] > target)
			{
				end--;
			}
			else
			{
				ans[0] = FindPosFront(nums, tmp[begin]);
				ans[1] = FindPosBack(nums, tmp[end]);
				break;
			}
		}
		return ans;
	}
};

复杂度分析：

时间复杂度：O（ $N*\log_{}{N}$ ），其中是数组中的元素个数，快速排序的时间复杂度为O（ $N*\log_{}{N}$ ），其余循环时间复杂度均为O（），因此取快速排序的时间复杂度。

空间复杂度：O（），开辟了一个N个大小的临时数组。

方法3：哈希表

方法3分析：

我们发现方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们很容易想到建立哈希映射，这样便可以将寻找 target - x 的时间复杂度降低到O（N）降低到 O（1）。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，后续遍历到 target-x 时，便可以与之前插入的 x 进行配对，这样即可保证不会让 x 和自己匹配。

代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        vector<int> ans(2);
        for (int i = 0; i < nums.size(); ++i) 
        {
            auto it = hashtable.find(target - nums[i]); //查找对应元素在不在哈希表内
            if (it != hashtable.end()) //对应元素在哈希表中就直接返回结果
            {
                ans[0] = it->second;
                ans[1] = i;
            }
            else //不在则添加本元素，等到循环遍历到对应元素时，则可以查找到本元素
            {
                hashtable[nums[i]] = i;
            }
        }
        return ans;
    }
};