LeetCode (Algorithms#15) ‒ 3Sum

Problem

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.

Example:

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

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

Solution

The problem is a direct extension of2Sum, which runs in $O(n)$. With 3Sum, it should be reasonable to assume that a $O(n^2)$ solution is possible. The trick is in handling repeated combinations of the same three numbers, which I initially tried using a hashset of solutions, with a sum of each number's hash to hash to a solution. This worked, but was too slow for one of the tests.

The better approach is to first sort the array, and then while considering each of the $n$ numbers, use a left and right pointer, and while moving them inward, solve the 2Sums problem with a target of $-n$. To iterate the left and right pointers, we chose to increase the left pointer if the sum is less than 0, and decrease the right pointer if the sum is greater than the 0. Since the array is sorted, increasing or decreasing either pointer will change the sum to the next lowest or highest value, respectively, ensuring that no solution is skipped. We can simultaneously skip over any numbers on both the left and right side that are repeats to ensure only a new solution is considered. The code below implements this approach.

Time complexity: $O(n^2)$
Space complexity: $O(n^2)$
Runtime: 82 ms (77.86%)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> sums = new ArrayList<List<Integer>>(); if (nums==null || nums.length < 3) return sums; Arrays.sort(nums); int l, r, v, len = nums.length; List<Integer> L; for (int i=0; i<len-1; i++) { if (i>0 && nums[i-1]==nums[i]) continue; l = i+1; r = len-1; while (l < r) { v = nums[i]+nums[l]+nums[r]; if (v < 0) l++; else if (v > 0) r--; else { // sum == 0 L = new ArrayList<Integer>(3); L.add(nums[i]); L.add(nums[l]); L.add(nums[r]); sums.add(L); v=nums[l++]; while (l<r && nums[l]==v) l++; v=nums[r--]; while (r>l && nums[r]==v) r--; } } } return sums; }