目录
两数之和：
对应letecode链接：
题目描述：
给定一个整数数组 nums?和一个整数目标值 target，请你在该数组中找出 和为目标值 target??的那?两个?整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：输入：nums = [3,3], target = 6
输出：[0,1]
?提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗
方法一：暴力枚举：??
💖思考方式：
最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。
当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。但是时间复杂度较高为0（N^2)
具体过程：
预定义：外循环指针i，内循环指针j，给定值target，给定数组arr
初始化：i=0，j=i+1，len=arr.length-1
step1：外循环i∈[0，len] , 内循环j∈[i+1,len]，判断arr[i]+arr[j]=target? 如果满足则返回i，j 。
step2：如果不满足上述条件，那么继续循环，直到循环完成，因为问题定义肯定有解，所以在循环结束前一定可以找到满足条件的值。
?💖实现代码：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int len=nums.size(); for(int i=0;i<len-1;i++){ for(int j=i+1;j<len;j++){ if(nums[i]+nums[j]==target) return {i,j}; } } return {};//匿名对象 } };
方法二：哈希表空间换时间????
💖思考方式：
哈希可以快速查找一个数字。
建立哈希表，key等于数组的值，value等于值所对应的下标。
然后遍历数组，每次遍历到位置i时，检查 target-num[i] 是否存在，注意target-num[i]的位置不能等于i。
下图以示例演示一下哈希表，将数组插入到哈希表中，查找给定的key，即可以在O(1) 的时间复杂度查找到，图中的a、b、c、d指的是哈希表的索引。
?💖实现代码：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int>hashMap; for(int i=0;i<nums.size();i++){ if(hashMap.count(target-nums[i])){ return {i,hashMap[target-nums[i]]}; } hashMap[nums[i]]=i;//插入 } return {}; } };
两数之和II
对应letecode链接：
方法一：双指针????
💖思考方式：
思路：应以left和right指针，初始分别在数组的两端，然后不断判断两个指针指向的数字之和 和target的大小，和大了 ，right左移一位，和小了，left右移一位
复杂度：时间复杂度O(n)，数组总共遍历一次。空间复杂度O(1)
💖解题图示：
💖实现代码：
class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int left=0; int right=numbers.size()-1; while(left<right){ int sum=numbers[left]+numbers[right];//记录这两个数的和 if(sum<target)left++; else if(sum>target)right--; else return {left+1,right+1};//返回对应下表，匿名对象的形式返回 } return {};//没找到返回空 } };
三数之和：
对应letecode链接：?
题目描述：
给你一个包含 n 个整数的数组?nums，判断?nums?中是否存在三个元素 a，b，c ，使得?a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：输入：nums = []
输出：[]
示例 3：输入：nums = [0]
输出：[]提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
方法一：排序加三指针????
💖思考方式：
果我们将上个题目得指针解法称做是双指针的话，那么这个题目用到的方法就是三指针，因为我们是三数之和嘛，一个指针对应一个数，下面我们看一下具体思路，其实原理很简单，我们先将数组排序，直接 sort() 解决，排序之后处理起来就很容易了。下面我们来看下三个指针的初始位置。
?
初始情况见上图，我们看当前情况，三数之和为 -3 ，很显然不是 0 ，那么我们应该怎么做呢？
我们设想一下，我们当前的三数之和为 -3 < 0 那么我们如果移动橙色指针的话则会让我们的三数之和变的更小，因为我们的数组是有序的，所以我们移动橙色指针（蓝色不动）时和会变小，如果移动蓝色指针（橙色不动）的话，三数之和则会变大，所以这种情况则需要向右移动我们的蓝色指针，找到三数之和等于 0 的情况进行保存，如果三数之和大于 0 的话，则需要移动橙色指针，途中有三数之和为 0 的情况则保存。直至蓝橙两指针相遇跳出该次循环，然后我们的绿指针右移一步，继续执行上诉步骤。但是这里我们需要注意的一个细节就是，我们需要去除相同三元组的情况，我们看下面的例子。
这里我们发现 0 - 1 + 1 = 0，当前情况是符合的，所以我们需要存入该三元组，存入后，蓝色指针向后移动一步，橙色指针向前移动一步，我们发现仍为 0 -1 + 1 = 0 仍然符合，但是如果继续存入该三元组的话则不符合题意，所以我们需要去重。这里可以借助HashSet但是效率太差，不推荐。这里我们可以使用 while 循环将蓝色指针移动到不和刚才相同的位置，也就是直接移动到元素 0 上，橙色指针同样也是。则是下面这种情况，这样我们就实现了去重，然后继续判断当前三数之和是否为 0 。
💖动图展示：
?💖实现代码：
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int>>ans;//记录答案 int len=nums.size(); for(int i=0;i<len;i++){ if(i>0&&nums[i-1]==nums[i])continue;//去重 int left=i+1; int right=len-1; //双指针向后枚举 while(left<right){ int sum=nums[i]+nums[left]+nums[right]; if(sum<0)left++; else if(sum>0)right--; else{//等于0了 //将其放入容器中 ans.push_back({nums[i],nums[left],nums[right]}); //去重 while(left<right&&nums[left+1]==nums[left])left++; while(left<right&&nums[right-1]==nums[right])right--; left++; right--; } } } return ans; } };
这个题还有一种方法：回溯在这里就只给出代码，铁子们可以自己下去分析一下：
class Solution { public: vector<vector<int>>res; vector<int>tmp; void ksum(int k,int start,int target,vector<int>&nums) { int len=nums.size(); if(k>2) { for(int i=start;i<len;i++) { if(i>start&&nums[i-1]==nums[i])continue; tmp.push_back(nums[i]); ksum(k-1,i+1,target-nums[i],nums); tmp.pop_back(); } } else if(k==2) { int left=start; int right=len-1; while(left<right) { int sum=nums[left]+nums[right]; if(sum<target) { do { left++; }while(left<right&&nums[left-1]==nums[left]); } else if(sum>target) { do { right--; }while(left<right&&nums[right+1]==nums[right]); } else { tmp.push_back(nums[left]); tmp.push_back(nums[right]); res.push_back(tmp); tmp.pop_back(); tmp.pop_back(); while(left<right&&nums[left]==nums[left+1]) { left++; } while(left<right && nums[right]==nums[right-1]) { right--; } left++; right--; } } } } vector<vector<int>> threeSum(vector<int>& nums) { if(nums.size()<3) { return res; } sort(nums.begin(),nums.end()); ksum(3,0,0,nums); return res; } };
下面我们再来看一道和三数之和思路差不多的：
最近的三数之和：
对应letecode链接：
题目描述：
给你一个长度为 n 的整数数组?nums?和 一个目标值?target。请你从 nums 中选出三个整数，使它们的和与?target?最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：输入：nums = [0,0,0], target = 1
输出：0提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
方法一：排序加三指针????
💖思考方式：
与上题基本是一样的本题只是要找最接近的三个数。所以我们只要记录最接近的三个数之和即可：
?💖实现代码：
class Solution { public: int threeSumClosest(vector<int>& nums, int target) { int len=nums.size(); int res=0; int tmp=INT_MAX; sort(nums.begin(),nums.end()); for(int i=0;i<len;i++) { int left=i+1; int right=len-1; while(left<right) { int sum=nums[i]+nums[left]+nums[right]; if(sum==target) { return sum; } else if(sum>target)right--; else left++; int diff=abs(sum-target);//记录相差的值 if(diff<tmp)//更新最小差值 { tmp=diff; res=sum; } } } return res; } };
最后一道题：
四数之和：
对应letecode链接：
题目描述：
给你一个由 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
你可以按 任意顺序 返回答案 。示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
💖思考方式：
我们已经完成了两数之和和三数之和，这个题目应该就手到擒来了，因为我们已经知道这类题目的解题框架，两数之和呢，我们就先固定第一个数 ，然后移动指针去找第二个符合的，三数之和，固定一个数，双指针去找符合情况的其他两位数，那么我们四数之和，也可以先固定两个数，然后利用双指针去找另外两位数。所以我们来搞定他吧。
三数之和是，我们首先确定一个数，然后利用双指针去找另外的两个数，我们在这个题目里面的解题思路是需要首先确定两个数然后利用双指针去找另外两个数，和三数之和思路基本一致很容易理解。我们具体思路可以参考下图。
这里需要注意的是，我们的 target 不再和三数之和一样为 0 ，target 是不固定的，所以解题思路不可以完全照搬上面的题目。另外这里也需要考虑去重的情况，思路和上题一致。
?图则为我们查找到一个符合条件的四元组的情况，查找成功之后，下一步移动蓝色指针，重新定义绿蓝指针，继续执行上面步骤。
?💖实现代码：
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int len=nums.size(); vector<vector<int >>res; if(len<4) return res; sort(nums.begin(),nums.end()); for(int i=0;i<len;i++) { if(i>0&&nums[i-1]==nums[i]) { continue; } for(int j=i+1;j<len-1;j++) { if(j>i+1&&nums[j-1]==nums[j])//去重 { continue; } int left=j+1; int right=len-1; while(left<right) { long long sum=(long long )nums[i]+(long long)nums[j]+(long long )nums[left]+(long long )nums[right];//将其强转为long long 是为了防止溢出整型 if(sum>target) right--; else if(sum<target) left++; else { res.push_back({nums[i],nums[j],nums[left],nums[right]}); while(left<right&&nums[left+1]==nums[left])left++; while(left<right&&nums[right]==nums[right-1]) right--; left++; right--; } } } } return res; } };
最后：💖结束语:
🙌🙌🙌🙌
结语：对于个人来讲，在leetcode上进行探索以及单人闯关是一件有趣的时间，一个程序员，如果不喜欢编程，那么可能就失去了这份职业的乐趣。刷到我的文章的人，我希望你们可以驻足一小会，忙里偷闲的阅读一下我的文章，可能文章的内容对你来说很简单，(^▽^)不过文章中的每一个字都是我认真专注的见证！希望您看完之后，若是能帮到您，劳烦请您简单动动手指鼓励我，我必回报更大的付出~
