[数据结构与算法] LeetCode 热题 HOT 100 -＞ 1.两数之和

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode 热题 HOT 100 -＞ 1.两数之和 -> 正文阅读

[数据结构与算法]LeetCode 热题 HOT 100 -＞ 1.两数之和

题干描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和?为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

LeetCode原题链接

方法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（ $N^2$ ），其中 $N$ ?是数组中的元素个数，最坏情况下数组中任意两个数都要被匹配一次。

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

方法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}$ ），其中 $N$ ?是数组中的元素个数，快速排序的时间复杂度为O（ $N*\log_{}{N}$ ），其余循环时间复杂度均为O（ $N$ ），因此取快速排序的时间复杂度。

空间复杂度：O（ $N$ ），开辟了一个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;
    }
};