分析

• 本题的考点：双指针。

• 本题的暴力解法是三种循环枚举三个数，时间复杂度是$O(n^3)$的，不可取。

• 为了使用双指针，首先对数组进行排序，然后我们可以用i枚举三个数中的其中一个，然后使用双指针j、k找到另外两个数。这里假设i < j < k。

• 对于当前考虑的nums[i]，此时可以看成定值，我们初始化j = i+1, k = nums.size()-1，如果有$nums[i]+nums[j]+nums[k]\ge 0$，则当j增大时，k必须减小，否则两者都增大的话，三者之和会增大，而我们要找到三者之和为0的数据，不符合要求。这类似于对撞指针。

• 另外还要考虑不能出现重复答案，因为是排序后的数组，当我们遍历到相同元素直接跳过即可。

代码

• C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) break;  // 后面两个数一定大于等于nums[i]，可以直接退出
            if (i && nums[i] == nums[i - 1]) continue;
            // 双指针算法
            for (int j = i + 1, k = nums.size() - 1; j < k; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k--;
                if (nums[i] + nums[j] + nums[k] == 0) {
                    res.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }
        return res;
    }
};

• Java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;  // 后面两个数一定大于等于nums[i]，可以直接退出
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            // 双指针算法
            for (int j = i + 1, k = nums.length - 1; j < k; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k--;
                if (nums[i] + nums[j] + nums[k] == 0) {
                    res.add(get(nums[i], nums[j], nums[k]));
                }
            }
        }
        return res;
    }

    private List<Integer> get(int a, int b, int c) {
        List<Integer> res = new ArrayList<>();
        res.add(a); res.add(b); res.add(c);
        return res;
    }
}

时空复杂度分析

• 时间复杂度：$O(n^2)$，n为数组长度。因为外层循环中每次循环都会执行一次双指针算法，双指针算法时间复杂度是$O(n)$的，因此总体时间复杂度为$O(n^2)$的。

• 空间复杂度：$O(1)$。