d******l
发帖数: 175 | 1 大家好，我纠结这道题目一些时间了。期间用Java写了3个算法，在Judge Large的时候
都说超时。请教高人帮忙分析一下我的一个算法的复杂度（基于TwoSum的一个解法）。
非常感谢。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public ArrayList> twoSum(int[] numbers, int target) {
ArrayList> twoSumList = new ArrayList
Integer>>();
Map map = new HashMap();
for (int i = 0; i < numbers.length; ++ i) {
if (!map.containsKey(numbers[i])) {
map.put(target - numbers[i], i);
} else {
ArrayList res = new ArrayList();
res.add(numbers[map.get(numbers[i])]);
res.add(numbers[i]);
twoSumList.add(res);
}
}
return twoSumList;
}
public ArrayList> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
int len = num.length;
if (len < 3) {
return new ArrayList>();
}
ArrayList> resList = new ArrayList
Integer>>();
for (int i = 0; i < len; ++ i) {
int[] num_excluded = getExcludedArray(num, i);
ArrayList> twoSumList = twoSum(num_excluded,
-num[i]);
if (twoSumList.size() == 0) {
continue;
}
for (ArrayList twoSumRes : twoSumList) {
ArrayList resArrayList = (ArrayList)
twoSumRes.clone();
resArrayList.add(num[i]);
Collections.sort(resArrayList);
if (!resList.contains(resArrayList)) {
resList.add(resArrayList);
}
}
}
return resList;
}
int[] getExcludedArray(int[] num, int index) {
int[] newArray = new int[num.length - 1];
int i = 0, j = 0;
while ( i < num.length) {
if (i != index) {
newArray[j] = num[i];
++ j;
}
++ i;
}
return newArray;
}
} |
s********s
发帖数: 49 | 2 代码好长啊。。。其实有了2sum,3sum的做法很直观吧：先取出一个数，那么只要在剩
下的数字里面找到两个数字使得他们的和等于(target – 那个取出的数)就可以了吧。
所以3sum就退化成了2sum, 取出一个数字，这样的数字有N个，所以3sum的算法复杂度
就是O(N^2 )。
注意你排序只需要排一次，后面的工作都是取出一个数字，然后找剩下的两个数字，找
两个数字是2sum用头尾指针线性扫，这里很容易错误的将复杂度算成O(N^2 log N)，这
个是不对的。
可以参考这个总结 http://tech-wonderland.net/blog/summary-of-ksum-problems.html |
d******l
发帖数: 175 | 3 感谢回复！我现在的解法就是像你说的，把原来的数组取出一个数来做2sum（2sum使用
hashmap来做的）。我没有一开始就排序，而是没得到一个2sum以后，把当前拿出来的
那个元素跟2sum的结果并在一起得到resArrayList。再对resArrayList排序。由于
resArrayList只包含3个元素，所以应该对整体复杂度没有什么影响。然后再通过判断
这个resArrayList是不是已经存在于最后的解resList里面，不存在的话，就resList.
add(resArrayList)。我现在还没有明白解法里面是哪儿导致复杂度太高。。。可否请
你再帮忙分析一下？
再次感谢发的链接。 |
g**G
发帖数: 767 | 4 Did you consider to skip duplicate element?
I pasted my solution as follows, hope it helps
public ArrayList> threeSum(int[] num) {
ArrayList> threeSum = new ArrayList
Integer>>();
if (num == null || num.length == 0)
return threeSum;
Arrays.sort(num);
int len = num.length;
int prev1 = Integer.MIN_VALUE;
int prev2 = Integer.MIN_VALUE;
int prev3 = Integer.MIN_VALUE;
for (int i = 0; i < len - 2; i++) {
if (prev1 == num[i])
continue;
int left = i + 1;
int right = len - 1;
// direction == 1: move from left to right;
// direction == 2: move from right to left;
int direction = 0;
while (left < right) {
if (direction == 1 && num[left] == prev2) {
left++;
continue;
} else if (direction == 2 && num[right] == prev3) {
right--;
continue;
}
int sum = num[i] + num[left] + num[right];
if (sum == 0) {
ArrayList temp = new ArrayList();
temp.add(num[i]);
temp.add(num[left]);
temp.add(num[right]);
threeSum.add(temp);
prev2 = num[left++];
direction = 1;
} else if (sum < 0) {
prev2 = num[left++];
direction = 1;
} else {
prev3 = num[right--];
direction = 2;
}
}
prev1 = num[i];
}
return threeSum;
} |
g**G
发帖数: 767 | 5 看了一遍你的写法，首先是每个元素都拿出来去和另外的n-1个元素去求twosum这一步
就不是很好，因为已经检验过的元素就不用再拿出来了，这样势必会增加很多重复元素
，在大数据时会稍微耗时
你后来用contains判断duplicate，其实你每一步contains都是要遍历一遍resarray的
，你resarray长度为m的话，复杂度就是o（mn）了
尽量要把去重这个问题扼杀在襁褓阶段
{
【在 d******l 的大作中提到】
: 大家好，我纠结这道题目一些时间了。期间用Java写了3个算法，在Judge Large的时候
: 都说超时。请教高人帮忙分析一下我的一个算法的复杂度（基于TwoSum的一个解法）。
: 非常感谢。
: import java.util.ArrayList;
: import java.util.Arrays;
: import java.util.Collections;
: import java.util.HashMap;
: import java.util.Map;
: public class Solution {
: public ArrayList> twoSum(int[] numbers, int target) {
|
d******l
发帖数: 175 | |
