本文总结力扣上的求和问题。

两数之和

1. 两数之和：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

两数之和的求解是哈希表的经典用法。如果我们直接使用二重循环枚举，时间复杂度为 $O(N^2)$ ，空间复杂度为 $O(1)$ 。用哈希表可以省下一个循环的开销，时间复杂度为 $O(N)$ ，代价是空间复杂度变为 $O(N)$ 。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> ump;//定义哈希表
        for (int i = 0; i < nums.size(); i++){
            if (ump.count(target - nums[i])){//一旦target - nums[i]是哈希表的key，则配对成功
                return{ i, ump[target - nums[i]] };//返回对应的下标即可
            }
            ump[nums[i]] = i;//以nums[i]为key，以i为value存哈希表
        }
        return {-1,-1};
    }
};

两数之和II

167. 两数之和 II - 输入有序数组：给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 1 开始计数，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

两数之和II是二分查找的经典用法。需要遍历数组一次确定第一个数，时间复杂度是 $O(n)$ ，寻找第二个数使用二分查找，时间复杂度是 $O(\log n)$ ，因此总时间复杂度是 $O(n \log n)$ ，空间复杂度是 $O(1)$ 。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); ++i) {
            int low = i + 1, high = numbers.size() - 1;
            while (low <= high) {//注意这里有等号，low==high可能一开始就成立
                int mid = (high + low) / 2;
                if (numbers[mid] == target - numbers[i]) {//==
                    return {i + 1, mid + 1};
                } else if (numbers[mid] > target - numbers[i]) {//>
                    high = mid - 1;
                } else {//<
                    low = mid + 1;
                }
            }
        }
        return {-1, -1};
    }
};

此外，我们还可以使用双指针。从两端逐渐向中间移动，直到成功配对，两个指针移动总次数最多为 $N$ ，时间复杂度是 $O(N)$ ，空间复杂度是 $O(1)$ 。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int low = 0, high = numbers.size() - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return {low + 1, high + 1};
                //从两端逐渐向中间移动，直到成功配对
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return {-1, -1};
    }
};

三数之和

15. 三数之和：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

本题和【两数之和】类似，但是难度高了不少。难点有二，一是少循环，二是去重复。

为保证不重复，我们首先进行排序，然后要求枚举过程满足：

$a<b<c$ 严格成立；
需要和上一次枚举的数不相同。

为了减少时间复杂度，仅对 $a$ 进行枚举，对 $b$ 、 $c$ 使用双指针查找。

当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 $O(N^2)$ 减少到 $O(N)$ 。为什么是 $O(N)$ 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的 b），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 $O(N)$ ，均摊下来，每次也向左移动一个位置，因此时间复杂度为 $O(N)$ 。

注意到我们的代码中还有第一重循环，时间复杂度为 $O(N)$ ，因此枚举的总时间复杂度为 $O(N^2)$ 。由于排序的时间复杂度为 $O(N \log N)$ ，在渐进意义下小于前者，因此算法的总时间复杂度为 $O(N^2)$ 。

我们忽略存储答案的空间，额外的排序的空间复杂度为 $O(\log N)$ 。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 $O(N)$ 。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;//随b递增，c是递减的，不需要每个循环初始化third=n-1
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({ nums[first], nums[second], nums[third] });
                }
            }
        }
        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

你可以按任意顺序返回答案。

本题和【三数之和】类似，解法也相似。即先排序，再两重循环枚举a、b，最后双指针c、d。

两重循环格式：

for (int i = 0; i < length - 3; i++) {
    for (int j = i + 1; j < length - 2; j++) {
        ...
    }
}

使用两重循环分别枚举前两个数，然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数。假设两重循环枚举到的前两个数分别位于下标 i 和 j，其中 i<j。初始时，左右指针分别指向下标 j+1和下标 n−1。每次计算四个数的和，并进行如下操作：

如果和等于 target，则将枚举到的四个数加到答案中，然后将左指针右移直到遇到不同的数，将右指针左移直到遇到不同的数；
如果和小于 target，则将左指针右移一位；
如果和大于target，则将右指针左移一位。

使用双指针枚举剩下的两个数的时间复杂度是 $O(N)$ ，因此总时间复杂度是 $O(N^3)$ ，低于 $O(N^4)$ 。

具体实现时，还可以进行一些剪枝操作：

在确定第一个数之后，如果 nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target，说明此时剩下的三个数无论取什么值，四数之和一定大于 target，因此退出第一重循环；
在确定第一个数之后，如果nums[i]+nums[n-1]+nums[n-2]+nums[n-3]<target，说明此时剩下的三个数无论取什么值，四数之和一定小于 target，因此第一重循环直接进入下一轮；
在确定前两个数之后，如果 nums[i]+nums[j]+nums[j+1]+nums[j+2]>target，说明此时剩下的两个数无论取什么值，四数之和一定大于target，因此退出第二重循环；
在确定前两个数之后，如果nums[i]+nums[j]+nums[n-1]+nums[n-2]<target，说明此时剩下的两个数无论取什么值，四数之和一定小于 target，因此第二重循环直接进入下一轮。

额外的排序的空间复杂度为 $O(\log N)$ ，此外修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 $O(N)$ 。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> quadruplets;
        if (nums.size() < 4) {
            return quadruplets;
        }
        sort(nums.begin(), nums.end());
        int length = nums.size();
        for (int i = 0; i < length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            long long sumTemp = (long long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3];
            //sumTemp防止int爆了
            if (sumTemp > target) {
                break;//剪枝1
            }
            if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                continue;//剪枝2
            }
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;//剪枝3
                }
                if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;//剪枝4
                }
                int left = j + 1, right = length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        quadruplets.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;//左指针右移直到遇到不同的数
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;//右指针左移直到遇到不同的数
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
};

star2dust

【力扣刷题】求和问题（二分查找+双指针）

两数之和

两数之和II

三数之和

四数之和

静态指针与指向静态类型的指针