双指针 - 两数求和问题[E]
优质
小牛编辑
133浏览
2023-12-01
001.Two Sum[E]
1.题目
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
2.思路
作为我们可能进入leetcode遇到的第一题,大家对它可谓是又爱又恨,而且它确实又有很多解法,总结起来可以有以下3种,3种还都能A过….
2.1双重循环
最简单的思路,两重循环,没啥技术含量,速度很慢,毕竟是$O(N^2)$
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
for(int i = 0;i < nums.size();i++)
{
for(int j = i+1;j < nums.size();j++)
if(nums[i] + nums[j] == target)
{
result.push_back(i);
result.push_back(j);
return result;
}
}
}
};
2.2 排序
其实简单的想,用一个排序都能把复杂度降到$O(NlogN)$,通过排序,然后用两个指针从前后扫描逼近真值(注意这个思想,可以让O(N*N)的复杂度降为O(N),充分利用排序,因为一定会有一个值满足,然后通过值去原数组里找对应的下标(这里其实就可以考虑,如果当初就用一个数据结构存好键值对应关系就好了,其实就是hashmap,下面的做法就用到了)
(下面代码是 dugu9sword写的java代码,我就没写成c++的,主要看思路,还是比较好理解的)
public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] nums_sorted=new int[nums.length];
System.arraycopy(nums,0,nums_sorted,0,nums.length);
//Quicksort.
Arrays.sort(nums_sorted);
//Find the two numbers. O(n)
int start=0;
int end=nums_sorted.length;
while(start<end){
while(nums_sorted[start]+nums_sorted[--end]>target);
if(nums_sorted[end]+nums_sorted[start]==target)
break;
while(nums_sorted[++start]+nums_sorted[end]<target);
if(nums_sorted[end]+nums_sorted[start]==target)
break;
}
//find the indices of the two numbers
int[] ret=new int[2];
int index=0;
int a=nums_sorted[start];
int b=nums_sorted[end];
for(int i=0;i<nums.length;i++)
if(nums[i]==a || nums[i]==b)
ret[index++]=i;
return ret;
}
}
2.3 Hashmap
最后一种是比较聪明的做法,用hashmap,hashmap是内部存储方式为哈希表的map结构,哈希表可以达到查找O(1),哈希表的介绍可以看这里, C++实现Hashmap的方式,这里用unordered_map关联容器,可以实现键值对应。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
unordered_map<int,int> mymap;
int res;
for(int i = 0;i < nums.size();i++)
{
res = target - nums[i];
unordered_map<int,int>::iterator it = mymap.find(res);
if(it != mymap.end())
{
return vector<int>({it->second,i});
}
mymap[nums[i]] = i;
}
}
};