Archive for October 18th, 2013
[leetcode] 4Sum | 四个数加和等于x，不许重复
Posted on: October 18, 2013
和3sum一样，多加一维就多n的复杂度，这个是O(n^3)，没看到别人有什么好的做法。注意防止duplicate的地方都标红了，算是比较简洁的two pointers防止dup的方式，以后可以都这么些。
public ArrayList<ArrayList> fourSum(int[] num, int target) {
ArrayList<ArrayList> result = new ArrayList<ArrayList>();
Arrays.sort(num);
for (int i = 0; i < num.length; i++) {
if (i > 0 && num[i] == num[i - 1])
continue;
for (int j = i + 1; j < num.length; j++) {
if (j > i + 1 && num[j] == num[j - 1] ) //一开始写的j > 0，就把1111 x=4的组合给漏掉了
continue;
int p = j + 1, q = num.length - 1;
while (p < q) {
int sum = num[i] + num[j] + num[p] + num[q];
if (sum == target) {
ArrayList quad = new ArrayList();
quad.add(num[i]);
quad.add(num[j]);
quad.add(num[p]);
quad.add(num[q]);
result.add(quad);
do {p++;} while (p < q && num[p] == num[p - 1]);
do {q--;} while (p < q && num[q] == num[q + 1]);
} else if (sum < target) {
p++;
} else {
q--;
}
}
}
}
return result;
}
Tags: array, twoPointers
本来以为是弱智题，但是要求不能duplicate之后，发现代码还真不好写了。难怪通过率只有16%这么低。
- 如何处理“和上一个一样就不要做了”这种duplicate情况？（形成自己的代码习惯）
- if (i > 0 或类似condition && num[i] == num[i – 1]) continue;
- 这样可以保证永远笼罩在while (some condition)的保证之下，用continue就不会出现越界等情况。
- 如果是递归，外层没有while，则用while (boundary && num[i] == num[i – 1[) {i++;}
public ArrayList<ArrayList> threeSum(int[] num) {
ArrayList<ArrayList> result = new ArrayList<ArrayList>();
Arrays.sort(num);
for (int i = 0; i < num.length; i++) {
if (i > 0 && num[i] == num[i - 1])
continue;
int x = 0 - num[i];
int p = i + 1, q = num.length - 1;
while (p < q) {
if (p > i + 1 && num[p] == num[p - 1]) {
p++;
continue;
}
if (q < num.length - 1 && num[q] == num[q + 1]) {
q--;
continue;
}
if (num[p] + num[q] == x) {
ArrayList triple = new ArrayList();
triple.add(num[i]);
triple.add(num[p]);
triple.add(num[q]);
result.add(triple);
} else if (num[p] + num[q] < x) {
p++;
} else {
q--;
}
}
}
return result;
}
Lexi's Leetcode solutions 