LeetCode 15 - 3 Sum

经典 3 Sum 问题

作者 QIFAN 日期 2017-01-11
LeetCode 15 - 3 Sum

原题链接:15. 3 Sum


题干

给定一个含有重复元素的数组,返回所有满足 a + b + c = 0 的组合(没有重复)。

思路

如果没有重复,就是如下的经典做法:

  • 排序
  • 遍历两两组合 nums[i]nums[j] ,利用二叉搜索在数组 [j + 1, length - 1] 的范围里找 nums[k] = -(nums[i] + nums[j])

时间复杂度为 $O(n^2)$ ,空间复杂度为 $O(1)$ 。

但由于含有重复元素,要避免重复结果。只要保证这一轮 i 所对应的值和上一轮 i 所对应的值不一样,以及这一轮 j 所对应的值和上一轮 j 所对应的值不一样。

代码:

public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums.length < 3) {
return res;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// 避免重复结果
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int lastj = 0;
for (int j = i + 1; j < nums.length - 1; j++) {
// 避免重复结果
if (j > i + 1 && nums[j] == nums[lastj]) {
continue;
}
int target = -(nums[i] + nums[j]);
int k = binarySearch(nums, target, j + 1, nums.length - 1);
// 如果存在 k
if (k != -1) {
List<Integer> tuple = new ArrayList<>();
tuple.add(nums[i]);
tuple.add(nums[j]);
tuple.add(nums[k]);
res.add(tuple);
}
lastj = j;
}
}
return res;
}
private int binarySearch(int[] nums, int target, int lo, int hi) {
// base case
if (lo > hi) {
return -1;
}
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
return binarySearch(nums, target, mid + 1, hi);
}
return binarySearch(nums, target, lo, mid - 1);
}