Three Sum

前后双指针夹逼

---

015 Three Sum

中等

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

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

分析：

题解1

执行用时：33 ms, 在所有 Java 提交中击败了20.57%的用户内存消耗：43.7 MB, 在所有 Java 提交中击败了62.90%的用户

算法珠玑上的解法先排序，然后左右夹逼，时间复杂度O(n^2)

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums.length < 3) return result;//少于三个无结果
    Arrays.sort(nums);//从小到大排序

    for (int i = 0; i < nums.length - 2; ++i) {
        //i为固定的位，前后两位相同的就不再重复固定了
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        int j = i + 1;//前指针
        int k = nums.length - 1;//后指针
        while (j < k) {
            if (nums[i] + nums[j] + nums[k] < 0) {
                ++j;//前指针后移
                //相同的跳过
                while (nums[j] == nums[j - 1] && j < k) ++j;
            } else if (nums[i] + nums[j] + nums[k] > 0) {
                --k;//后指针前移
                while (nums[k] == nums[k + 1] && j < k) --k;
            } else {
                //满足条件的添加到结果list中
                result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                ++j;
                --k;
                while (nums[j] == nums[j - 1] && j < k) ++j;
                while (nums[k] == nums[k + 1] && j < k) --k;
            }
        }
    }
    return result;
}

---