双指针算法：三数之和

三数之和

题目描述

给定一个整数数组 nums，判断是否存在三个元素 a, b, c，使得 a + b + c = 0？找出所有满足条件且不重复的三元组。

算法原理

解法一：暴力枚举 排序后使用三重循环枚举，配合 Set 去重。效率较低。

解法二：双指针算法 在排序的基础上进行优化。固定一个数 nums[i]，问题转化为两数之和。使用左右指针 left 和 right 分别指向 i+1 和数组末尾。

1. 若 nums[left] + nums[right] > target，右指针左移。
2. 若 nums[left] + nums[right] < target，左指针右移。
3. 若相等，记录结果并移动指针，同时跳过重复元素。 注意：当 nums[i] > 0 时可直接结束，因为后续不可能有和为 0 的组合。

代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i = 0; i < n; ) {
            if(nums[i] > 0) break;
            int left = i + 1, right = n - 1, target = -nums[i];
            while(left < right) {
                int sum = nums[left] + nums[right];
                if(sum > target) {
                    right--;
                } else if(sum < target) {
                    left++;
                } else {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + ]) right--;
                }
            }
            i++;
            (i < n && nums[i] == nums[i - ]) i++;
        }
         ret;
    }
};