3 Sum

LintCode 3 Sum

Question

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

Analysis

考虑non-descending，先sort数组，其次考虑去除duplicate； 类似2sum，可以利用two pointers，不断移动left 和 right 指针，直到找到目标，或者两指针相遇

一重循环i遍历数组，作为a，其余两个指针left和right分别对应b，c。这样最终时间复杂度为 O(n^2)。

> Time Complexity O(n^2)
> Space Complexity O(1)

https://leetcode.com/problems/3sum/discuss/169885/Python-or-tm

固定区间的Two-Pointer

大概思路是外围for-loop一遍数组，然后在每次迭代的时候，设置[l, r]的区间，区间范围为l , r = i + 1, len(nums) - 1, 这样比对的数就有3个，分别是nums[i], nums[l] 和 nums[r].

最终要达到的效果是:

nums[l] + nums[r] == -nums[i]

这道题一定要记住去重，不仅仅是区间的l和r要去重，外围的i也需要去重。去重的方法如下:

i去重：if i == 0 or nums[i] > nums[i-1]:

l去重：while l < r and nums[l] == nums[l-1]: l += 1

r去重：while l < r and nums[r] == nums[r+1]: r -= 1

Solution

Two Pointers - (40ms, 97.77%)

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = nums.length - 1;
            int target = 0 - nums[i];

            while (j < k) {
                if (nums[j] + nums[k] > target) {
                    k--;
                } else if (nums[j] + nums[k] < target) {
                    j++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));

                    j++;
                    k--;

                    // skip duplicates
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                }
            }
        }
        return res;
    }
}

Another Two Pointer

public class Solution {
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
    public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (numbers == null || numbers.length < 3) {
            return result;
        }
        Arrays.sort(numbers);

        for (int i = 0; i < numbers.length - 2; i++) {
            if (i > 0 && numbers[i] == numbers[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = numbers.length - 1;

            while (left < right) {
                int sum = numbers[i] + numbers[left] + numbers[right];
                if (sum == 0) {
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(numbers[i]);
                    tmp.add(numbers[left]);
                    tmp.add(numbers[right]);
                    result.add(tmp);
                    left++;
                    right--;
                    while (left < right && numbers[left] == numbers[left - 1]) {
                        left++;
                    }
                    while (left < right && numbers[right] == numbers[right + 1]) {
                        right--;
                    }
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }

            }
        }
        return result;
    }
}

Reference

• 九章算法题解 3 Sum

• MIT Paper Ilya Baran: Subquadratic Algorithms for 3SUM