15. 三数之和

题目链接

解题思路：拆分问题，三数之和，我们可以固定一个数字，就变成了两数之和了。还有一个难点就是，如何去重？

• 1️⃣先排序。

• 2️⃣固定第一个数，「第一个数」必须是之前没有求过的答案。

• 3️⃣从剩下的数中，求两数之和，求的过程中，直接去重。

  • 两数之和，因为是有序了，所以直接双指针

• 细节看代码

代码

class Solution {
public:

    // nums是有序的，在[L, R]上，求出和为target，放在res中，要求没有重复的
    void TwoSum(vector<int> &nums, int L, int R, int target, vector<pair<int, int>> &res) {
        int i = L;     // 左指针
        int j = R;     // 右指针
        while(i < j) {    // 保证必须有两个数以上
            while (i > L && i < j && nums[i] == nums[i - 1]) {     // 例如 1,1,1,2,2,2   假设现在i是第二个1，我们就要跳过
                i++;
            }
            if (i >= j) {    // 如果移动的过程中，没有两个数了   跳出
                break;
            }
            while(j < R && j > i && nums[j] == nums[j + 1]) {    // 同理  去重
                j--;
            }
            if (i >= j) {
                break;
            }
            if (nums[i] + nums[j] == target) {
                res.push_back({nums[i], nums[j]});
                i++;
                j--;
            } else if(nums[i] + nums[j] > target) {    // 右指针往左动
                j--;
            } else {
                i++;
            }
        }
    }


    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int i = 0;
        vector<vector<int>> ans;
        while(i + 2 < n) {    // 保证至少有三个数
            while(i > 0 && i < n && nums[i] == nums[i - 1]) {    // 去重
                i++;
            }
            if(i + 2 >= n) {    // 没有三个数了
                break;
            }
            vector<pair<int, int>> tmp;
            TwoSum(nums, i + 1, n - 1, -nums[i], tmp);
            for (auto &it : tmp) {
                ans.push_back({nums[i], it.first, it.second});
            }
            i++;
        }
        return ans;
    }
};