g***j
发帖数: 1275 | 1 如果返回vector >的话，如何保证结果是unique的？
比如输入是{0，0，0，0}，结果就是两个{0，0，0}，这样难道在push到vector的时候
就要一个一个check么？
当然如果用set就不存在这样的问题。
请问，有什么改进的算法，可以从根本上解决这个duplication的问题？
谢谢了。 | r*****e
发帖数: 792 | 2 if (num[low]+num[mid]+num[high]==0) {
do {--high;} while (num[high]==num[high+1]);
do {++mid;} while (num[mid]==num[mid-1]);
while (low
}
For low, should use while instead of do while because we don't want to
increment low if unnecessary.
In short, move the indices to positions that result in different num[index]
values.
【在 g***j 的大作中提到】
: 如果返回vector >的话，如何保证结果是unique的？
: 比如输入是{0，0，0，0}，结果就是两个{0，0，0}，这样难道在push到vector的时候
: 就要一个一个check么？
: 当然如果用set就不存在这样的问题。
: 请问，有什么改进的算法，可以从根本上解决这个duplication的问题？
: 谢谢了。
| g********E
发帖数: 178 | 3 1，第一层循环的时候跳过重复的；
2，第二层循环从两头跳过循环的；
vector< vector > threeSum(vector &num){
int n = num.size();
vector< vector > res;
vector cur;
sort(num.begin(), num.end());
for(int i = 0; i < n-2; i++){
if(i > 0 && num[i] == num[i-1]) continue;
cur.push_back(num[i]);
int start = i + 1, end = n - 1;
while(start < end){
if(start > i+1 && num[start] == num[start-1]) {
start++; continue;
}
if(end < n-1 && num[end] == num[end+1]){
end--; continue;
}
int sum = num[i] + num[start] + num[end];
if(sum == 0) {
cur.push_back(num[start]);
cur.push_back(num[end]);
res.push_back(cur);
cur.resize(1);
start++;
end--;
}
else if(sum > 0) end--;
else start++;
}
cur.pop_back();
}
return res;
} | j**7
发帖数: 143 | 4 public ArrayList> threeSum(int[] numbers) {
Arrays.sort(numbers);
ArrayList> list = new ArrayList
>>();
for (int i = 0; i < numbers.length; i++) {
if (i > 0 && numbers[i] == numbers[i - 1]) {
continue;
}
twoSumWhile(numbers, 0 - numbers[i], i + 1, list);
}
return list;
}
public void twoSumWhile(int[] numbers, int target, int start, ArrayList<
ArrayList> list) {
int index = start - 1;
int end = numbers.length - 1;
while (start < end) {
int sum = numbers[start] + numbers[end];
if (sum == target) {
ArrayList temp = new ArrayList();
temp.add(numbers[index]);
temp.add(numbers[start]);
temp.add(numbers[end]);
list.add(temp);
do {
start++;
end--;
} while (start < end && numbers[start] == numbers[start - 1]
&& numbers[end] == numbers[end + 1]);
} else if (target < sum) {
end--;
} else {
start++;
}
}
} |
|
