算法

(双指针) $O(n^2)$

本题是$Two\ Sum$的进阶版，对$a + b + c = 0$进行移项就会变成$b+c=-a$。所以我们可以固定这个$a$，我们就可以以数组中的每一个元素$nums[i]$作为$a$的值，然后对于数组中剩下的其他元素，我们都去找是否存在$(b,c)$这样的二元组，使得$b+c=-a$，如果找到了，那么他就是满足条件的三元组，如果没找到就把$a$替换成下一个$nums[i]$。

时间复杂度

每个$nums[i]$都会跑一个$two\ sum$的过程，时间复杂度就会是$O(n^2)$。

Java 代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; ++i) { // 三元组长度是3，所以a遍历到nums[n-3]即可
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 外去重
            int target = 0 - nums[i];
            int start = i + 1;
            int end = n - 1;
            while (start < end) {
                int sum = nums[start] + nums[end];
                if (sum == target) {
                    res.add(Arrays.asList(nums[i], nums[start++], nums[end--]));
                    // 内去重
                    while (start < end && nums[start] == nums[start - 1]) start++;
                    while (start < end && nums[end] == nums[end + 1]) end--;
                }
                else if (sum < target) start++;
                else end--;
            }
        }
        return res;
    }
}