两数之和

https://leetcode-cn.com/problems/two-sum/

两数之和Ⅱ：输入有序数组

https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
y总在三数之和中有一段代码一直理解不了，就是下面这一段，特别是K-1是什么意思？

  1.  for (int j = i + 1, k = nums.size() - 1; j < k; j ++ ) {
  2.     if (j > i + 1 && nums[j] == nums[j - 1]) continue;
  3.        while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k -- ;
  4.            if (nums[i] + nums[j] + nums[k] == 0) {
  5.                res.push_back({nums[i], nums[j], nums[k]});
  6.    }
  7. }

其实这段代码的对应问题就是有序数组中的两数之和，即在数组中找到和为target的两个下标
while(i < j -1 && numbers[i] + numbers[j-1] >= target) j—;
这段代码有一种探测的思想，我要找一个等于target的数。但是我的下一个（即比我小的数）都大于我要找的target，那我自身肯定不行，就要继续向下探测，找下一个。**更重要的是在探测的过程中避免了重复使用相同的元素[k]！！！**
下面是167题的两段代码，这两段代码都能通过，但是第一段代码避免了重复使用元素，第二段没有避免，都能通过的原因是找到【i，j】就返回了，如果让返回所有可能情况，第二段代码就过不去了比如【1，1，7，7】，让你返回等于8的下标，并且要求不可以重复使用相同的元素。第一段代码只会返回【0，3】，第二段代码会返回【【0，3】，【1，2】】这就重复使用了相同元素**

  1. //代码1：避免重复使用相同的元素
  2. class Solution {
  3. public:
  4.     vector<int> twoSum(vector<int>& numbers, int target) {
  5.         for(int i = 0 , j = numbers.size()-1 ; i < j ; i++){
  6.             if(i != 0 && numbers[i] == numbers[i-1]) continue;
  7.             while(i < j -1 && numbers[i] + numbers[j-1] >= target) j--;
  8.             if(numbers[i] + numbers[j] == target) return {i+1,j+1};
  9.         } 
  10.         return {};
  11.     }
  12. };
  13. //代码2：没有避免重复使用相同的元素
  14. class Solution {
  15. public:
  16.     vector<int> twoSum(vector<int>& numbers, int target) {
  17.         for(int i = 0 , j = numbers.size()-1 ; i < j ; i++){
  18.             while(i < j && numbers[i] + numbers[j] > target) j--;
  19.             if(numbers[i] + numbers[j] == target) return {i+1,j+1};
  20.         } 
  21.         return {};
  22.     }
  23. };
  24. //代码3：和代码2一样可以通过，没有避免重复使用相同的元素
  25. class Solution {
  26. public:
  27.     vector<int> twoSum(vector<int>& numbers, int target) {
  28.        int i = 0 , j = numbers.size() -1;
  29.        while(i < j){
  30.            if(numbers[i] + numbers[j] == target) return {i+1,j+1};
  31.            else if(numbers[i] + numbers[j] > target) j--;
  32.            else i++;
  33.        }
  34.        return {};
  35.     }
  36. };

三数之和

https://leetcode-cn.com/problems/3sum/
先看第一种比较好理解的解决方法:注意第9行开始就是上面一题代码3while(i < j){}模式下的去重操作，比较好理解，但是代码没有y总的简洁

  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& nums) {
  4.         vector<vector<int>> res;
  5.         sort(nums.begin(),nums.end());
  6.         for(int i = 0 , x = nums.size(); i < x ; i++){
  7.             if(i != 0 && nums[i] == nums[i-1]) continue;
  8.             int j = i + 1 , k = nums.size() - 1;
  9.             while(j < k){
  10.                 if(nums[j] + nums[k] == -nums[i]){
  11.                     res.push_back({nums[i],nums[j],nums[k]});
  12.                     j++;k--;
  13.                     while(j < k && nums[j] == nums[j-1]) j++;
  14.                     while(j < k && nums[k] == nums[k+1]) k--;
  15.                 }else if(nums[j] + nums[k] > -nums[i]){
  16.                     k--;
  17.                 }else{
  18.                     j++;
  19.                 }
  20.             }
  21.         }
  22.         return res;
  23.     }
  24. };

最后上y总代码！！！！

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i = 0 , x = nums.size(); i < x ; i++){
            if(i != 0 && nums[i] == nums[i-1]) continue;
            int target = -nums[i];
            for(int j = i + 1 , k = nums.size() - 1; j < k ; j++){
                if(j != i+1 && nums[j-1] == nums[j]) continue;
                //此处target即-nums[i]
                while(j < k-1 && nums[j] + nums[k-1] >= target) k--;
                if(nums[j] + nums[k] == target){
                    res.push_back({nums[i],nums[j],nums[k]});
                }
            }
        }
        return res;
    }
};

最接近的三数之和

https://leetcode-cn.com/problems/3sum-closest/
Image 1.png
总体思路和上一题三数之和是一致的，只不过把上面nums[i] + nums[j] + nums[k] = 0换成了nums[i] + nums[j] + nums[k] >= <target

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        pair<int,int> res(INT_MAX,INT_MAX);
        for(int i = 0 , x = nums.size() ; i < x ; i++){
            for(int j = i + 1 , k = x - 1 ; j < k ; j++){
                while(j < k - 1 && nums[i] + nums[j] + nums[k-1] >= target) k--;
                int s = nums[i] + nums[j] + nums[k];
                res = min(res,make_pair(abs(s-target),s));
                if(j < k-1){
                    s = nums[i] + nums[j] + nums[k-1];
                    res = min(res,make_pair(target-s,s));
                }
            }
        }
        return res.second;
    }
};

第十行为什么是abs(s-target)，加abs是因为，s不一定大于target。因为上面的while循环是两个条件①j < k - 1，②nums[i] + nums[j] + nums[k-1] >= target ，比如【-4，-1，1，2】1，第一轮-4+-1+1<1,退出了循环s = -3，s-target = -4,你不能说最小距离是-4吧。
下面的不加是因为保证了条件①并跳出了循环，那么肯定是条件②s>=target不满足，即s肯定小于target

四数之和

https://leetcode-cn.com/problems/4sum/
和上面的题一个思路了

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i = 0 , x = nums.size() ; i < x ; i++){
            if(i != 0 && nums[i-1] == nums[i]) continue;
            for(int j = i + 1 ; j < x ; j++){
                if(j != i + 1 && nums[j-1] == nums[j]) continue;
                for(int k = j + 1 , q = x - 1 ; k < q ; k++){
                    if(k != j + 1 && nums[k-1] == nums[k]) continue;
                    while(k < q-1 && nums[i] + nums[j] + nums[k] + nums[q-1] >= target)q--;
                    if(nums[i] + nums[j] + nums[k] + nums[q] == target){
                        res.push_back({nums[i],nums[j],nums[k],nums[q]});
                    }
                }
            }
        }
        return res;
    }
};