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:
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.For example, given array S = {-1 0 1 2 -1 -4},A solution set is: (-1, 0, 1) (-1, -1, 2)
Method:
Similar to 3 sum, we just need to skip duplicate numbers
Solution:
Time: O(nlogn) Space: O(1)
public class Solution { public ArrayList<ArrayList<Integer>> threeSum(ArrayList<Integer> A) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); Collections.sort(A); for (int i = 0; i < A.size() - 2; i ++) { if (i > 0 && A.get(i).equals(A.get(i - 1))) { continue; } int iVal = A.get(i); int j = i + 1; int k = A.size() - 1; while (j < k) { int jVal = A.get(j); int kVal = A.get(k); int candidate = iVal + jVal + kVal; if (candidate == 0) { result.add(new ArrayList<Integer>(Arrays.asList(iVal, jVal, kVal))); j ++; while (j < k && A.get(j).equals(A.get(j - 1))) { j ++; } } else if (candidate > 0) { k --; } else if (candidate < 0) { j ++; } } } return result; } }
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if (nums == null || nums.length == 0) { return result; } Arrays.sort(nums); int n = nums.length; for (int i = 0; i < n; i ++) { if (i > 0 && nums[i - 1] == nums[i]) { continue; } int left = i + 1; int right = n - 1; while (left < right) { if (left > i + 1 && nums[left - 1] == nums[left]) { left ++; continue; } int sum = nums[i] + nums[left] + nums[right]; if (sum > 0) { right --; } else if (sum < 0) { left ++; } else { result.add(Arrays.asList(nums[i], nums[left], nums[right])); left ++; right --; } } } return result; } }