15. 3Sum (Medium) Facebook Microsoft Amazon Bloomberg Adobe
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]
]
Solution 1: sort + Two Pointers O(n^2); O(1)
/**
* Two Pointers O(n^2);O(1)
* Sort given array first.
* Traverse the array with 1 pointer i.
* Use another 2 pointers from both start(i + 1) and end to find the rest 2 target elements.
* How to avoid duplicate? Compare current number with the previous one, if same, skip.
* How to early prune? When current number is positive, stop.
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) {
return res;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) {
break; // Pruning. Stop at positive integers.
}
if (i > 0 && nums[i] == nums[i - 1]) { //当前数在之前已经出现过，跳过
continue; // Skip duplicate.
}
int l = i + 1;
int r = nums.length - 1;
int sum = 0 - nums[i];
while (l < r) {
if (nums[l] + nums[r] == sum) {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
while (l < r && nums[l] == nums[l + 1]) { // Skip duplicate.
l++;
}
while (l < r && nums[r] == nums[r - 1]) { // Skip duplicate.
r--;
}
l++; //这两行不能忘记
r--;
} else if (nums[l] + nums[r] < sum) {
while (l < r && nums[l] == nums[l + 1]) { // Skip duplicate.可以不写
l++;
}
l++;
} else {
while (l < r && nums[r] == nums[r - 1]) { // Skip duplicate. 可以不写
r--;
}
r--;
}
}
}
return res;
}
Solution 2: sort + HashMap O(n^2); O(n)
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 3) {
return res;
}
Arrays.sort(nums); //还是需要排序的
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.containsKey(nums[i]) ? map.get(nums[i]) + 1 : 1);
}
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
int rest = 0 - nums[i] - nums[j];
int count = 0;
if (nums[i] == rest) {
count++;
}
if (nums[j] == rest) {
count++;
}
if (map.containsKey(rest) && map.get(rest) > count && rest >= nums[j]) {
res.add(Arrays.asList(nums[i], nums[j], rest));
}
while (j < nums.length - 1 && nums[j] == nums[j + 1]) {
j++;
}
}
while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
i++;
}
}
return res;
}
Solution 3: HashMap + HashSet O(n^2); O(n)
public List<List<Integer>> threeSum(int[] nums) {
// 统计每个数字的个数
HashMap<Integer, Integer> counts = new HashMap<>();
for (int value : nums) {
counts.put(value, counts.getOrDefault(value, 0) + 1 );
}
List<List<Integer>> results = new ArrayList<>();
HashSet<Long> existence = new HashSet<>();
for (int l : nums) {
for (int r : nums) {
// 设三个数为l, m, r
// 为了"Permutation-去重"，只需要保留l <= m <= r的结果
int m = -(l + r);
if (l > m || m > r) {
continue;
}
// 用于加速的pre-check: m存在
int mc = counts.getOrDefault(m, 0);
if (mc == 0) {
continue;
}
// 拼接l,r进行identity去重
long code = ( (long)l << 32) | r;
if (existence.contains(code)) {
continue;
}
// l, m, r可能是两个或三个相同的数字
// 我们需要检查counts里对应的数字有那么多个
int lc = counts.getOrDefault(l, 0);
int rc = counts.getOrDefault(r, 0);
if (l == r && l == m) {
lc = lc - 3;
} else if (l == r || l == m ) {
lc = lc - 2;
} else if (m == r) {
mc = mc - 2;
} else {
lc --;
mc --;
rc --;
}
if (lc >= 0 && mc >= 0 && rc >= 0) {
results.add( new ArrayList<Integer>(Arrays.asList(l, m, r)) );
existence.add(code);
}
}
}
return results;
}
下面这种解法也可以，但是过不了LC最后一个testcase
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> set = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();
List<List<Integer>> output = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.containsKey(nums[i]) ? map.get(nums[i]) + 1 : 1);
}
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
int a = nums[i];
int b = nums[j];
int c = -nums[i] - nums[j];
if (map.containsKey(c)) {
int count = 1;
count += a == c ? 1 : 0;
count += b == c ? 1 : 0;
if (count <= map.get(c)) {
List<Integer> list = new ArrayList<>();
list.add(a);
list.add(b);
list.add(c);
int k = 0;
List<List<Integer>> perm = permutation(a, b, c);
for (; k < 6; k++) {
if (set.contains(perm.get(k))) {
break;
}
}
if (k == 6) {
set.add(list);
}
}
}
}
}
output.addAll(set);
return output;
}
private List<List<Integer>> permutation(int a, int b, int c) {
List<List<Integer>> res = new ArrayList<>();
res.add(Arrays.asList(a, b, c));
res.add(Arrays.asList(a, c, b));
res.add(Arrays.asList(b, a, c));
res.add(Arrays.asList(b, c, a));
res.add(Arrays.asList(c, a, b));
res.add(Arrays.asList(c, b, a));
return res;
}
public List<List<Integer>> threeSumC(int[] nums) { //还要对3个数排序，面试官一般不会同意
Set<List<Integer>> set = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();
List<List<Integer>> output = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.containsKey(nums[i]) ? map.get(nums[i]) + 1 : 1);
}
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
int a = nums[i];
int b = nums[j];
int c = -nums[i] - nums[j];
if (map.containsKey(c)) {
int count = 1;
count += a == c ? 1 : 0;
count += b == c ? 1 : 0;
if (count <= map.get(c)) {
List<Integer> list = new ArrayList<>();
int arr[] = new int[3];
arr[0] = a;
arr[1] = b;
arr[2] = c;
Arrays.sort(arr);
list.add(arr[0]);
list.add(arr[1]);
list.add(arr[2]);
if (!set.contains(list))
set.add(list);
}
}
}
}
output.addAll(set);
return output;
}
Follow Up:
- K sum，面试官想要的是recursion，我给了一个iteratively build hashset的方法，空间复杂度我后来想了想有点难看，但是时间做到了最优，面试官比较满意，也没有细问。这套题目能正确回答big o很重要，面试官很在乎。
- 没有重复数字
- 不能改变数组的顺序: 见Solution 3。
- 返回一组满足条件的值就行，follow up问数组里的值能重复使用怎么办？用了类似combination sum的方法递归求解。
- 返回有没有即可.