3 Sum

leetcode 15.

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.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution. When the array doesn’t has duplicate, it is a classical 3Sum problem, the code is like below

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> list = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;
            }
            else if (sum < 0) {
                right--;
            }
            else {
                left++;
            }
        }
    }
    return list;
}

If it has duplicate, we need to skip the duplicate by several rules:
1. When iterating i, if nums[i] has same value as the previous one, nums[i] == nums[i – 1]. We need to skip
2. After we found a new pair at nums[i], nums[left] and nums[right], we need to move left forward until a different value; move right backward until a different value.

public List<List<Integer>> threeSumWithDuplicate(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> list = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                left++;
                right--;
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            }
            else if (sum < 0) {
                right--;
            }
            else {
                left++;
            }
        }
    }
    return list;
}

Check my code on github.