LeetCode——Two Sum

最新推荐文章于 2021-11-27 22:42:27 发布

cassiePython

最新推荐文章于 2021-11-27 22:42:27 发布

阅读量573

点赞数

分类专栏：算法

本文链接：https://blog.csdn.net/cassiePython/article/details/46327463

版权

算法专栏收录该内容

34 篇文章

订阅专栏

本文介绍了LeetCode上的经典题目TwoSum的两种解决方案。首先是通过双重遍历的方式找到两个数的下标，其次利用哈希表提高查找效率，实现O(n)的时间复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

LeetCode——Two Sum

LeetCode上第一题：

题目如下：

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目翻译：

给定一个整数数组和一个目标整数，我们要做的是从这个整数数组中找出两个数，满足这两个数的值相加等于目标整数，返回这两个数的下标（从一开始）

这里假定每给一个目标整数总能找到这样的两个数，即不考虑不存在的情况。还要注意到这种情况，即这两个数是不同的（题目中隐含的）例如：给定一个

整数数组：numbers = { 2 3 4 } ，target = 6 返回的结果不是 2 ，2 而是 1, 3尽管 3+3 = 6

解题思路——第一种方法：

我们很容易想到的一个解法是只要遍历所有的元素，判断两个数的和是不是等于target就可以了，更简化一下是选定第一个数后，第二个数从第一个数的后一个数进行选取

或者这样想——选取第一个数之后，用target减去这个数，看得到的值是否在数组中。这样我们就得到了第一种方法：

<span style="font-size:14px;">vector<int> twoSum(vector<int>& nums, int target)
{
	vector<int> index;
	vector<int>::iterator iter = nums.begin();
	vector<int>::size_type ix = 0;
	vector<int>::const_iterator result;
	for(ix=0;ix<nums.size();++ix)
	{
		result = find(iter+ix+1,nums.end(),target-nums[ix]);
		if(result!=nums.end())
		{
			index.push_back(ix+1);
			index.push_back(result-iter+1);
			break;
		}
	}
	return index;
}</span>

这种方法很简单，但很遗憾leetcode不接受这个复杂度的算法，我们需要一种更快的算法。

解题思路——第二种方法：

这里我们需要使用C++ STL中的map容器

首先我们把整数数组的每一个值作为map容器的第一个参数输入，其对应的下标作为第二个参数输入，然后进行循环遍历数组，对于给定的target只需检测target减去选取的第一个数的值是否存在于map容器中。这样的话我们就得到了一个O(n)的算法。

<span style="font-size:14px;">vector<int> twoSum2(vector<int>& nums, int target)
{
	vector<int> index;
	map<int,int> mp;
	for(int i=0;i<nums.size();++i)
	{
		mp[nums[i]] = i;
	}
	map<int,int>::iterator iter;
	for(int j=0;j<nums.size();++j)
	{
		iter = mp.find(target-nums[j]);
		if(iter!=mp.end())
		{
			if(j==iter->second)
				continue;
			index.push_back(j+1);
			index.push_back(iter->second+1);
			break;
		}
	}
}</span>