LeetCode--15. 三数之和(C++描述)

// Source : https://leetcode.cn/problems/3sum/
// Date : 2022-5-15

class Solution {
public:
    vector> threeSum(vector& nums) {
        sort(nums.begin(), nums.end());
        vector> ans;
        // 枚举 a
        for (int i = 0; i < nums.size(); ++i) 
        {
            // 需要和上一次枚举的数不相同
            if (i > 0 && nums[i] == nums[i - 1]) 
                continue;
            // 转为求两数之和问题进行求解
            int target = -nums[i];
            // c 对应的指针初始指向数组的最右端
            int k = nums.size() - 1;
            // 枚举 b
            for (int j = i + 1; j < nums.size(); ++j) 
            {
                // 需要和上一次枚举的数不相同
                if (j > i + 1 && nums[j] == nums[j - 1]) 
                    continue;
                // 需要保证 b 的指针在 c 的指针的左侧
                while (j < k && nums[j] + nums[k] > target) 
                    --k;
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 bnums[i], nums[j], nums[k]});
            }
        }
        return ans;
    }
};