解题思路

• 暴力法搜索为 O(N^3) 时间复杂度，可通过双指针动态消去无效解来优化效率。
• 双指针法铺垫： 先将给定 nums 排序，复杂度为 O(NlogN)
• 双指针法思路： 固定 3 个指针中最左（最小）数字的指针 k，双指针 i，j 分设在数组索引 (k, len(nums)) 两端，通过双指针交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：

1. 当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 3 个数字都大于 00 ，在此固定指针 k 之后不可能再找到结果了。
2. 当 k > 0 且 nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
3. i，j 分设在数组索引 (k, len(nums)) 两端，当i < j时循环计算s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：
   • 当s < 0时，i += 1并跳过所有重复的nums[i]；
   • 当s > 0时，j -= 1并跳过所有重复的nums[j]；
   • 当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合

图解

复杂度分析

时间复杂度 O(N^2)：其中固定指针k循环复杂度 O(N)，双指针 i，j 复杂度 O(N)。
空间复杂度 O(1)：指针使用常数大小的额外空间。

代码

// JAVA 
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < nums.length - 2; i++){
            // nums[k]为非负数，就不能满足a+b+c=0了
            if(nums[i] > 0) break;
            // 跳过计算过的数据，同时防止结果重复
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int leftPoint = i + 1, rightPoint = nums.length - 1;
            while(leftPoint < rightPoint){
                int sum = nums[i] + nums[leftPoint] + nums[rightPoint];
                if(sum < 0){
                    leftPoint++;
                } else if (sum > 0) {
                    rightPoint--;
                } else {
                    res.add(Arrays.asList(nums[i], nums[leftPoint], nums[rightPoint]));
                    while (leftPoint < rightPoint && nums[leftPoint] == nums[leftPoint+1]) {
                        leftPoint++;
                    }
                    while(leftPoint < rightPoint && nums[rightPoint] == nums[rightPoint-1]) {
                        rightPoint--;
                    }
                    leftPoint++;
                    rightPoint--;
                }
            }
        }
        return res;
    }
}

# python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        length = len(nums)
        if (not nums or length<3):
            return []
        for i in range(length):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            leftPoint, rightPoint = i + 1, length - 1
            while leftPoint < rightPoint:
                total = nums[i] + nums[leftPoint] + nums[rightPoint]
                if total < 0:
                    leftPoint += 1
                elif total > 0:
                    rightPoint -= 1
                else:
                    res.append([nums[i], nums[leftPoint], nums[rightPoint]])
                    while leftPoint < rightPoint and nums[leftPoint] == nums[leftPoint+1]:
                        leftPoint += 1
                    while leftPoint < rightPoint and nums[rightPoint] == nums[rightPoint-1]:
                        rightPoint -= 1
                    leftPoint += 1
                    rightPoint -= 1
        return res

// C++
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int > vtemp;
        sort(nums.begin(), nums.end()); // sort
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            int leftPoint = i + 1;
            int rightPoint = nums.size() - 1;
            while (leftPoint < rightPoint) {
                int sum = nums[leftPoint] + nums[rightPoint] + nums[i];
                if (sum < 0) {
                    leftPoint++;
                } else if(sum > 0) {
                    rightPoint--;
                } else{
                    vector<int > vtemp{nums[i], nums[leftPoint], nums[rightPoint]};
                    res.push_back(vtemp);
                    vtemp.clear();
                    while (leftPoint < rightPoint && nums[leftPoint] == nums[leftPoint+1]) {
                        leftPoint++;
                    }
                    while (leftPoint < rightPoint && nums[rightPoint] == nums[rightPoint-1]) {
                        rightPoint--;
                    }
                    leftPoint++;
                    rightPoint--;
                }
            }
        }
        return res;
    }   
};