1. 两数之和
难度简单
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
思路1：双重循环，时间复杂度O(n**2)
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); for (int i = 0;i<n;i++) { for (int j = i+1;j<n;j++) { if (nums[i]+nums[j] == target) return {i,j}; } } return {}; } };
思路2：unordered_map，因其查找复杂度可达到O（1），这道题的时间复杂度可达到O(n) ；
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> hash; int n = nums.size(); for (int i = 0;i<n;i++) { if (hash.find(target-nums[i])!=hash.end()) return {i,hash[target-nums[i]]}; else hash[nums[i]] = i; } return {}; } };
可见时间得到了优化的同时增加了空间的开销；
补充有关unordered_map的知识：
需要加入头文件
unordered_map的遍历，用迭代器，i->first,i->second，来访问key和val；
初始化不需要加" = "，创建新的key,val对和py的做法类似；
#include <iostream> #include <unordered_map> using namespace std; int main() { unordered_map<string,int>score{{"小明",98}}; score["张三"] = 93; for (unordered_map<string,int>::iterator i = score.begin();i!=score.end();i++) cout<<i->first<<" "<<i->second<<endl; }
难度中等
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
排序nlogn,双指针+循环 n**2，总复杂度 O(n**2)
思路：本题先排序，双指针才能起作用
**双指针算法最核心的用途就是优化时间复杂度，关注题目的单调性**
先定第一个数nums[i]，那么就转化为在[i,n-1]区间内做两数之和的问题,令target = -nums[i]；
如果用hash来做，在去重上会比较困难；
如果用双指针，迎刃而解；由于序列单调，两头和过大，r左移动，两头和过小，l右移动；
如果两头和(设为a,b)等于target，加入答案，然后l++,r--，如果nums[l] = nums[l-1]，往后移动，直到不等于a，同理右边一直移动直到不等于b;
特别的，由于已经排过序，那么当nums[i]（第一个数>0）的时候，必然无解，退出循环；
特别的，当nums[i] = nums[i-1]，意味着对于第一个数是nums[i]的这轮寻找可以不执行。原因在于，如果存在合法解j,k,使得nums[i]+nums[j]+nums[k]=0,那么对于nums[i-1]，j,k一定也是它的合法解，故一定会出现重复，所以就得到我们上述的结论，如果nums[i] = nums[i-1]，continue；
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; int n = nums.size(); sort(nums.begin(),nums.end()); for (int i = 0;i<n;i++) { if (nums[i]>0) break; if (i>0&&nums[i] == nums[i-1]) continue; int l = i+1, r = n-1,target = -nums[i]; while (l<r) { if (target == nums[l]+nums[r]) { ans.push_back({nums[i],nums[l],nums[r]}); l++; r--; while (nums[l] == nums[l-1]&&l<r) l++; while (nums[r] == nums[r+1]&&l<r) r--; } else if (target<nums[l]+nums[r]) r--; else l++; } } return ans; } };
18. 四数之和
难度中等
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
思路：两层循环o（n**2)+排序nlogn+双指针n
第一层循环固定第一个数，转化为三数之和；
第二层循环固定第二个数，转化为两数之和；
重点在于去重：
道理和三数之和中的特别的，当nums[i] = nums[i-1]，意味着对于第一个数是nums[i]的这轮寻找可以不执行。原因在于，如果存在合法解j,k,使得nums[i]+nums[j]+nums[k]=0,那么对于nums[i-1]，j,k一定也是它的合法解，故一定会出现重复，所以就得到我们上述的结论，如果nums[i] = nums[i-1]，continue；一样，如果nums[i] = num[i-1]，那么会出现重复的四元解；
如果nums[j] = nums[j-1]，那么会出现重复的三元解；
双指针内部的两层while,避免了重复的二元解；
！一些细节的地方，当我们判断nums[i] = nums[i-1]的时候，需要保证i>0;
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> ans; int n = nums.size(); if (n<4) return {}; sort(nums.begin(),nums.end()); for (int i = 0;i<n;i++) { if (i>0&&nums[i] ==nums[i-1])//四数之和去重 continue; int s3 = target - nums[i]; for (int j = i+1;j<n;j++) { if (j>i+1&&nums[j]==nums[j-1])//三数之和去重 continue; int s2 = s3 - nums[j];//两数之和 int l = j+1, r = n-1; while (l<r) { if (s2 == nums[l]+nums[r]) { ans.push_back({nums[i],nums[j],nums[l],nums[r]}); l++; r--; while (nums[l] == nums[l-1]&&l<r) l++; while (nums[r] == nums[r+1]&&l<r) r--;//两数之和去重 } else if (s2<nums[l]+nums[r]) r--; else l++; } } } return ans; } };
