15. 3Sum

/**

 * 15. 3Sum

 * Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0?

 * Find all unique triplets in the array which gives the sum of zero.

 * Notice that the solution set must not contain duplicate triplets.

 * Example 1:

 * Input: nums = [-1,0,1,2,-1,-4]

 * Output: [[-1,-1,2],[-1,0,1]]

 */

See my solution to the problem on github below:

https://github.com/zcoderz/leetcode/blob/main/src/main/java/arrays/ThreeSum.java

https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/ThreeSum.java

The problem is asking to list all triplets which sum to 0. The algorithm is straight forward:

  1. Sort the numbers
  2. Iterate from left to right
  3. For each number in 2, iterate from indexes to the right of it that equate to sum (-1*the number)
  4. For finding the sum you run two pointers, one going right and the other left.
    1. If sum of left and right is less, move left forward
    1. If sum of left and right is more, move right left
    1. If sum is same record, and advance both left and right.
  5. Avoid duplicates in 2 & 4 above.

Here is the code:

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> listSums = new ArrayList<>();
    for (int i = 0; i < nums.length && nums[i] <= 0; i++) {
        if (i == 0 || nums[i - 1] != nums[i]) { //avoid duplicate checks
            findSums(nums[i], i + 1, nums, listSums);
        }
    }
    return listSums;
}

/**
 * Use a two pointer approach, start from smallest on left and largest on right then advance the right or left
 * pointer based on whether the sum from left and right indexes is less or greater than the target
 *
*/
void findSums(int start, int startIndex, int[] nums,
              List<List<Integer>> lSums) {
    int target = start * -1;
    int i = startIndex;
    int j = nums.length - 1;

    while (j > i) {
        int currSum = nums[i] + nums[j];
        if (currSum > target) {
            j--; //make currSum smaller
        } else if (currSum < target) {
            i++; //make currSum larger
        } else {
            lSums.add(Arrays.asList(start, nums[i], nums[j]));
            i++;
            j--;
            //advance pointers if repeated items
            //so that the next data set has a unique collection
            while (i < nums.length && nums[i] == nums[i - 1]) i++;
            while (nums[j] == nums[j + 1] && j > 0) j--;
        }
    }
}