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)
Solution:
Sorting helps us to deal with both constraints. Keep 3 pointers. We move the 1st pointer from left to right, and each time solve a 2SUM problem using the other 2 pointers in the subarray with index ranging from i + 1 to n.
Complexity: O(n^2).
Since 2SUM can be solved in O(n) time after sorting, or in O(n) time using HashMap.
Sorting helps us to deal with both constraints. Keep 3 pointers. We move the 1st pointer from left to right, and each time solve a 2SUM problem using the other 2 pointers in the subarray with index ranging from i + 1 to n.
Complexity: O(n^2).
Since 2SUM can be solved in O(n) time after sorting, or in O(n) time using HashMap.
public class Solution { private ArrayList<Integer> oneTriple(int a, int b, int c) { ArrayList<Integer> triple = new ArrayList<Integer>(); triple.add(a); triple.add(b); triple.add(c); return triple; } public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); ArrayList<List<Integer>> list
= new ArrayList<List<Integer>>(); for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int j = i + 1; int k = nums.length - 1; while (j < k) { int sum = nums[i] + nums[j] + nums[k]; if (sum == 0) { list.add(oneTriple(nums[i], nums[j], nums[k])); j++; k--; while (j < k && nums[j] == nums[j - 1]) { j++; } while (j < k && nums[k] == nums[k + 1]) { k--; } } else if (sum > 0) { k--; } else { j++; } } } return list; } }
No comments:
Post a Comment