15 3Sum

Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+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)

If the given array is not sorted, first sort the array.

Then, we need to take the first element by traversing the array from index 0 to index n-3 (n = length of the array)

Then, we have to take next two elements from i+1 to n-1 and check if the sum is 0.

Here, we can use binary search using the leftmost element and rightmost elements. If the sum is greater than 0, we can move the rightmost element towards left, otherwise, we can move the leftmost element towards right. In order to duplicate element, we have to move right and left if the two neighbor elements are same.

In order to avoid the duplicate of the solution, we don't have to check if the first element is same.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length == 0) return new ArrayList<List<Integer>>();
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;    // avoid duplicate
            int l = i+1, r = nums.length-1;
            while (l<r) {
                int sum = nums[i]+nums[l]+nums[r];
                if (sum > 0) r--;
                else if (sum < 0) l++;
                else {
                    result.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    //remove repeated values for left and right
                    while (l<r && nums[l]==nums[l+1]) l++;
                    while (l<r && nums[r]==nums[r-1]) r--;
                    l++;
                    r--;
                }
            }
        }
        return result;
    }
}