[leetcode] 3sum

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.

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

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

• Two Pointers

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

  public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> lists = new LinkedList<>(); Arrays.sort(nums); int sum; for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int start = i + 1; int end = nums.length - 1; while (start < end) { sum = nums[i] + nums[start] + nums[end]; if (sum == 0) { List<Integer> list = new ArrayList<>(); list.add(nums[i]); list.add(nums[start]); list.add(nums[end]); lists.add(list); start++; end--; while (start < end && nums[start] == nums[start - 1]) { start++; } while (start < end && nums[end] == nums[end + 1]) { end--; } } else if (sum > 0) { end--; } else { start++; } } } return lists; }

• HashMap

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

  //Runtime: 197 ms public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> lists = new ArrayList<>(); HashMap hashMap = new HashMap(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { hashMap.put(nums[i], i); } for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums.length - 1; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } int target = -(nums[i] + nums[j]); if (hashMap.containsKey(target) && (int)hashMap.get(target) > j) { List<Integer> list = new ArrayList<>(); list.add(nums[i]); list.add(nums[j]); list.add(target); lists.add(list); } } } return lists; }

• binarySearch

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

  //Runtime: 223 ms public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> lists = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums.length - 1; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) { continue; } int k = binarySearch(-(nums[i] + nums[j]),nums, j + 1); if (k > j) { List<Integer> list = new ArrayList<>(); list.add(nums[i]); list.add(nums[j]); list.add(nums[k]); lists.add(list); } } } return lists; } public static int (int key, int[] a, int start){ int lo = start; int hi = a.length - 1; while(lo <= hi){ int mid = lo + (hi - lo) / 2; if(key < a[mid]){ hi = mid - 1; }else if(key > a[mid]){ lo = mid + 1; }else{ return mid; } } return -1; }