@Test public void test() { assertThat(this.inst.threeSum(new int[] {}), empty()); assertThat(this.inst.threeSum(new int[] {1, 2 }), empty()); assertThat(this.inst.threeSum(new int[] {1, 2, 3, 4 }), empty()); final List<List<Integer>> res = this.inst.threeSum(new int[] {-1, 0, 1, 2, -1, -4}); log.debug("res: {}", res); assertThat(res, hasSize(2)); }
public List<List<Integer>> threeSum(int[] numbers) { final List<List<Integer>> result = new LinkedList<>(); if (numbers == null) { return result; } final int numsLen = numbers.length; if (numsLen <= 2) { return result; } Arrays.sort(numbers); final int min = numbers[0]; final int max = numbers[numsLen - 1]; if (min * 3 > 0 || max * 3 < 0) { return result; } for (int i = 0; i < numsLen - 2; ++i) { if (i != 0 && (numbers[i] == numbers[i - 1])) { continue; } int lo = i + 1; int hi = numsLen - 1; final int sum = 0 - numbers[i]; while (lo < hi) { if (numbers[lo] + numbers[hi] == sum) { result.add(Arrays.asList(numbers[i], numbers[lo], numbers[hi])); while (lo < hi && numbers[lo] == numbers[lo + 1]) { lo++; } while (lo < hi && numbers[hi] == numbers[hi - 1]) { hi--; } lo++; hi--; } else if (numbers[lo] + numbers[hi] < sum) { lo++; } else { hi--; } } } return result; }
ThreeSum { public List<List<Integer>> threeSum(int[] numbers) { final List<List<Integer>> result = new LinkedList<>(); if (numbers == null) { return result; } final int numsLen = numbers.length; if (numsLen <= 2) { return result; } Arrays.sort(numbers); final int min = numbers[0]; final int max = numbers[numsLen - 1]; if (min * 3 > 0 || max * 3 < 0) { return result; } for (int i = 0; i < numsLen - 2; ++i) { if (i != 0 && (numbers[i] == numbers[i - 1])) { continue; } int lo = i + 1; int hi = numsLen - 1; final int sum = 0 - numbers[i]; while (lo < hi) { if (numbers[lo] + numbers[hi] == sum) { result.add(Arrays.asList(numbers[i], numbers[lo], numbers[hi])); while (lo < hi && numbers[lo] == numbers[lo + 1]) { lo++; } while (lo < hi && numbers[hi] == numbers[hi - 1]) { hi--; } lo++; hi--; } else if (numbers[lo] + numbers[hi] < sum) { lo++; } else { hi--; } } } return result; } }
ThreeSum { public List<List<Integer>> threeSum(int[] numbers) { final List<List<Integer>> result = new LinkedList<>(); if (numbers == null) { return result; } final int numsLen = numbers.length; if (numsLen <= 2) { return result; } Arrays.sort(numbers); final int min = numbers[0]; final int max = numbers[numsLen - 1]; if (min * 3 > 0 || max * 3 < 0) { return result; } for (int i = 0; i < numsLen - 2; ++i) { if (i != 0 && (numbers[i] == numbers[i - 1])) { continue; } int lo = i + 1; int hi = numsLen - 1; final int sum = 0 - numbers[i]; while (lo < hi) { if (numbers[lo] + numbers[hi] == sum) { result.add(Arrays.asList(numbers[i], numbers[lo], numbers[hi])); while (lo < hi && numbers[lo] == numbers[lo + 1]) { lo++; } while (lo < hi && numbers[hi] == numbers[hi - 1]) { hi--; } lo++; hi--; } else if (numbers[lo] + numbers[hi] < sum) { lo++; } else { hi--; } } } return result; }  }
ThreeSum { public List<List<Integer>> threeSum(int[] numbers) { final List<List<Integer>> result = new LinkedList<>(); if (numbers == null) { return result; } final int numsLen = numbers.length; if (numsLen <= 2) { return result; } Arrays.sort(numbers); final int min = numbers[0]; final int max = numbers[numsLen - 1]; if (min * 3 > 0 || max * 3 < 0) { return result; } for (int i = 0; i < numsLen - 2; ++i) { if (i != 0 && (numbers[i] == numbers[i - 1])) { continue; } int lo = i + 1; int hi = numsLen - 1; final int sum = 0 - numbers[i]; while (lo < hi) { if (numbers[lo] + numbers[hi] == sum) { result.add(Arrays.asList(numbers[i], numbers[lo], numbers[hi])); while (lo < hi && numbers[lo] == numbers[lo + 1]) { lo++; } while (lo < hi && numbers[hi] == numbers[hi - 1]) { hi--; } lo++; hi--; } else if (numbers[lo] + numbers[hi] < sum) { lo++; } else { hi--; } } } return result; }  List<List<Integer>> threeSum(int[] numbers); }
ThreeSum { public List<List<Integer>> threeSum(int[] numbers) { final List<List<Integer>> result = new LinkedList<>(); if (numbers == null) { return result; } final int numsLen = numbers.length; if (numsLen <= 2) { return result; } Arrays.sort(numbers); final int min = numbers[0]; final int max = numbers[numsLen - 1]; if (min * 3 > 0 || max * 3 < 0) { return result; } for (int i = 0; i < numsLen - 2; ++i) { if (i != 0 && (numbers[i] == numbers[i - 1])) { continue; } int lo = i + 1; int hi = numsLen - 1; final int sum = 0 - numbers[i]; while (lo < hi) { if (numbers[lo] + numbers[hi] == sum) { result.add(Arrays.asList(numbers[i], numbers[lo], numbers[hi])); while (lo < hi && numbers[lo] == numbers[lo + 1]) { lo++; } while (lo < hi && numbers[hi] == numbers[hi - 1]) { hi--; } lo++; hi--; } else if (numbers[lo] + numbers[hi] < sum) { lo++; } else { hi--; } } } return result; }  List<List<Integer>> threeSum(int[] numbers);  }