经典算法问题2：两数之和、三数之和、四数之和、N数之和

记录整理一下两数之和、三数之和、四数之和等的解题套路。

1. 两数之和

要判断一个元素是否出现过，典型的是使用哈希表来求，因为题目说只要返回一个结果就可以了，所以我们这里就使用unordered_map就行了（重复也没有问题），明确了这点代码就好写了。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int cnt = 0;
        int m = nums.size();
        unordered_map<int, int> mp;
        for (int i = 0; i < m; ++i)
        {
            if (mp.count(target - nums[i]) == 0)
                mp.insert({nums[i], i});
            else
            {
                cnt = mp[target - nums[i]];
                return {cnt, i};
            }
        }
        return {-1, -1};
    }
    
};

15. 三数之和

可以看一下灵神的视频两数之和 三数之和【基础算法精讲 01】，更好地了解双指针，思路也挺清晰的，注意两个点，如果nums[i] + nums[i + 1] + nums[i + 2] > 0，后面也不需要继续遍历了，如果nums[i] + nums[len - 2] + nums[len - 1] < 0，i可能还可以变大，这时候直接continue：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        for (int i = 0; i < len - 2; ++i)
        {
            
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0)
                break;
            if (nums[i] + nums[len - 2] + nums[len - 1] < 0)
                continue;
            int j = i + 1;
            int k = len - 1;
            while (j < k)
            {
                if (nums[i] + nums[j] + nums[k] < 0)
                {
                    j++;
                }
                else if (nums[i] + nums[j] + nums[k] > 0)
                {
                    k--;
                }
                else
                {
                    ans.push_back({nums[i], nums[j], nums[k]});
                    j++;
                    while (j < k && nums[j] == nums[j - 1])
                        j++;
                    k--;
                    while (j < k && nums[k] == nums[k + 1])
                        k--; 
                }
            }
            
            
        }
        return ans;
    }
};

16. 最接近的三数之和

和三数之和是差不多的，也是先排序，定义一个diff表示最后的三数之和和target的差值绝对值，ans表示最后的三数之和。类似三数之和的思路，我们可以对i，j，k三个数进行去重：

1. 对i的去重

if (i > 0 && nums[i] == nums[i - 1])
    continue;

1. 对j的去重

while (j < k && nums[j] == nums[j + 1])
    j++;

1. 对k的去重

while (j < k && nums[k] == nums[k - 1])
    k--;

代码优化的思路只要是nums[i] + nums[i + 1] + nums[i + 2]（这里用s表示）比target大，后面的数只会大不会小了，所以这时候我们和diff进行比较，然后更新ans，并收获结果：

if (s > target)
{
    if (s - target < diff)
        ans = s;
    break;
}

以及nums[i] + nums[len - 1] + nums[len - 2]（这里用s表示）比target小，这时候应该continue，不过这时候我们还是需要和diff比较一下，更新ans和diff。

if (s < target)
{
    if (target - s < diff)
    {
        ans = s;
        diff = target - s;
    }
    continue;
}

可以参考灵神的分析，写得特别好：极致优化！基于三数之和的做法（Python/Java/C++/Go/JS）

class Solution {
public:

    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        int ans = nums[0] + nums[1] + nums[2];

        int diff = (ans - target >= 0) ? (ans - target) : (target - ans);
        for (int i = 0; i < len - 2; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int s = nums[i] + nums[i + 1] + nums[i + 2];
            if (s > target)
            {
                if (s - target < diff)
                    ans = s;
                break;
            }

            s = nums[i] + nums[len - 1] + nums[len - 2];
            if (s < target)
            {
                if (target - s < diff)
                {
                    ans = s;
                    diff = target - s;
                }
                continue;
            }

            int j = i + 1;
            int k = len - 1;
            while (j < k)
            {
                int s = nums[i] + nums[j] + nums[k];
                int diffCur = (s - target >= 0) ? (s - target) : (target - s);
                if (diffCur == 0)
                    return target;
                else if (s < target)
                {
                    if (diffCur < diff)
                    {
                        ans = s;
                        diff = diffCur;
                    }
                    while (j < k && nums[j] == nums[j + 1])
                        j++;
                    j++;
                }
                else if (s > target)
                {
                    if (diffCur < diff)
                    {
                        ans = s;
                        diff = diffCur;
                    }
                    while (j < k && nums[k] == nums[k - 1])
                        k--;
                    k--;
                }
            }
        }
        return ans;
    }
};

18. 四数之和

还是使用双指针的写法，但是大数可能会溢出，比如下面的测试用例：

[0,0,0,1000000000,1000000000,1000000000,1000000000]
1000000000

所以这里判断使用long 类型

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        for (int i = 0; i < len - 3; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
                break;
            if ((long)nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target)
                continue;
            for (int j = i + 1; j < len - 2; ++j)
            {
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
                    break;
                if ((long)nums[i] + nums[j] + nums[len - 1] + nums[len - 2] < target)
                    continue;
                
                int k = j + 1;
                int p = len - 1;
                while (k < p)
                {
                    long s = (long)nums[i] + nums[j] + nums[k] + nums[p];
                    if (s < target)
                        k++;
                    else if (s > target)
                        p--;
                    else
                    {
                        ans.push_back({nums[i], nums[j], nums[k], nums[p]});
                        k++;
                        while (k < p && nums[k] == nums[k - 1])
                            k++;
                        p--;
                        while (k < p && nums[p] == nums[p + 1])
                            p--;
                    }
                }
            }
        }
        return ans;
    }
};

454. 四数相加 II

直观的想法是使用四个for循环，但那样时间复杂度会是 O ( n 4 ) O(n^4) O(n4)，没想清楚看了题解，可以用哈希表的方法来做，分而治之的方法，定义一个cnt来保存元组的个数。先处理前面两个数组，生成一个key为两个数组元素和以及value为数组元素和出现的次数的map。然后处理后两个数组，用0减去这两个数组的元素后查找在map是否有对应的元素，然后cnt增加对应的value（匹配到的元素）。分而治之时间复杂度变成 O ( n 2 ) O(n^2) O(n2)。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> mp; 
        int cnt = 0;
        for (int i = 0; i < nums1.size(); i++)
        {
            for (int j = 0; j < nums2.size(); ++j)
            {
                mp[nums1[i] + nums2[j]]++;
            }
        }
        for (int i = 0; i < nums3.size(); ++i)
        {
            for (int j = 0; j < nums4.size(); ++j)
            {
                if (mp.count(-nums3[i] - nums4[j]) != 0)
                    cnt += mp[-nums3[i] - nums4[j]];               
            }
        }
        return cnt;
    }
};

拓展：N数之和

如果给一个数组和一个target，要求N数之和等于target的N元组（不重复），又该怎么写呢？

我们可以用递归解决，如果清楚了四数之和的思路，我们发现每次先固定一个数，然后去找三数之和满足要求，再固定三数中的一个数，再去找两数之和满足要求，这样递归的思路就很清晰了，下面的代码用递归的方法解了四数之和，一样可以通过：

class Solution {
public:
    vector<vector<int>> nSum(int n, vector<int>& nums, int target, int begin)
    {
        if (n == 2)
            return twoSsum(nums, target, begin, nums.size() - 1);
        vector<vector<int>> res;

        for (int i = begin; i < nums.size() - (n - 1); ++i)
        {
            if (i > begin && nums[i] == nums[i - 1])
                continue;
            long s1 = nums[i];
            long s2 = nums[i];
            for (int j = 1; j < n; ++j)
            {
                s1 += nums[i + j];
                s2 += nums[nums.size() - j];
            }
            if (s1 > target)
                return res;
            if (s2 < target)
                continue;
            vector<vector<int>> tempVec = nSum(n - 1, nums, target - nums[i], i + 1);
            for (auto& vec: tempVec)
            {
                vec.insert(vec.begin(), nums[i]);
                res.push_back(vec);
            }
        }
        return res;
    }
    vector<vector<int>> twoSsum(vector<int>& nums, int target, int begin, int end)
    {
        vector<vector<int>> ans;

        while (begin < end)
        {
            long s = (long)nums[begin] + nums[end];
            if (s < target)
            {
                begin++;
            }
            else if (s > target)
            {
                end--;
            }
            else
            {
                ans.push_back({nums[begin], nums[end]});
                begin++;
                while (begin < end && nums[begin] == nums[begin - 1])
                    begin++;
                end--;
                while (begin < end && nums[end] == nums[end + 1])
                    end--;
            }

        }
        return ans;
    }
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        
        vector<vector<int>> ans;
        if (nums.size() < 4)
            return ans;
        sort(nums.begin(), nums.end());
        
        return nSum(4, nums, target, 0);
    }
};