15. 3Sum
Tags: ‘Array’, ‘Two Pointers’
Given an array nums of n integers, are there elements a, b, c in nums 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.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Solution
方法1：先排序，左右夹逼。O(n^2) O(1) 这个方法可扩展至k-sum：先排序，做k-2次循环，最内层左右夹逼
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// for each element, run a bidirectional sweep of 2sum for following elements
Arrays.sort(nums);
List<List<Integer>> result = new LinkedList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int lo = i + 1, hi = nums.length - 1, sum = 0 - nums[i];
while (lo < hi) {
if (nums[lo] + nums[hi] == sum) {
result.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
while (lo < hi && nums[lo] == nums[lo+1]) lo++; // skip duplicates when result foun
while (lo < hi && nums[hi] == nums[hi-1]) hi--;
lo++;
hi--;
} else if (nums[lo] + nums[hi] < sum) {
while (lo < hi && nums[lo] == nums[lo+1]) lo++;
lo++;
} else {
while (lo < hi && nums[hi] == nums[hi-1]) hi--;
hi--;
}
}
}
return result;
}
}
方法2： hashmap 做缓存(仅当需要返回数值而不是index时可以用) O(n^2) O(n)
不如第一种方法。 更少的空间，更易理解，且更加general
public List<List<Integer>> threeSum(int[] nums) {
// 一个值做hashmap， 两个值循环
List<List<Integer>> result = new LinkedList<>();
if (nums == null || nums.length < 3) return result;
Arrays.sort(nums);
Map<Integer, Integer> cache = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// There can be duplicate indexes, but doesn't matter since we only need value
cache.put(nums[i], i);
}
Set<String> used = new HashSet<>();
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;
Integer index = cache.get(0 - nums[i] - nums[j]);
if (index == null) {
continue;
} else {
if (index <= j) continue; // overlap
Integer[] temp = new Integer[] {nums[i], nums[j], nums[index]};
String key = Arrays.toString(temp);
if (!used.contains(key)) {
used.add(key);
result.add(Arrays.asList(temp));
}
}
}
}
return result;
}