public class Solution {
public List<List> threeSum(int[] nums) {
List<List> res = new ArrayList<List>();
int len = nums.length;
if(len < 3) {
return res;
}
Arrays.sort(nums);
for(int i = 0; i < len; i++) {
if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
//这个if在于去掉第一个数的重复的地方，不能跟前面的一个相等
int begin = i + 1;
int end = len - 1;
while(begin < end) {
int sum = nums[i] + nums[begin] + nums[end];
if(sum == 0) {
List list = new ArrayList();
list.add(nums[i]);
list.add(nums[begin]);
list.add(nums[end]);
res.add(list);
begin ++;
end --;
//这里在于去掉第二个数重复的地方，只要跟后面的相等就跳过
while(begin < end && nums[begin] == nums[begin-1]) {
begin ++;
}
//这里就是第三个重复的地方，只要跟前面的相等就跳过
while(begin < end && nums[end] == nums[end+1]) {
end --;
}
} else if(sum > 0) {
end --;
} else {
begin ++;
}
}
}
}
return res;
}
}
Shawngbk
commented
7 years ago
先对数组进行排序，时间复杂度O(log(n))，然后定好一个数的位置，查找另外两个数的和等于-nums[i]的组合，由于数组排好序了，所以可以从两边往中间走，当结果大于0的时候后边往后退一步，否则前边进一步，时间复杂度O(n^2)，所以时间复杂度为O（n^2）
public class Solution {> threeSum(int[] nums) {
List<List> res = new ArrayList<List>();
int len = nums.length;
if(len < 3) {
return res;
}
Arrays.sort(nums);
for(int i = 0; i < len; i++) {
if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
//这个if在于去掉第一个数的重复的地方，不能跟前面的一个相等
int begin = i + 1;
int end = len - 1;
while(begin < end) {
int sum = nums[i] + nums[begin] + nums[end];
if(sum == 0) {
List list = new ArrayList();
list.add(nums[i]);
list.add(nums[begin]);
list.add(nums[end]);
res.add(list);
begin ++;
end --;
//这里在于去掉第二个数重复的地方，只要跟后面的相等就跳过
while(begin < end && nums[begin] == nums[begin-1]) {
begin ++;
}
//这里就是第三个重复的地方，只要跟前面的相等就跳过
while(begin < end && nums[end] == nums[end+1]) {
end --;
}
} else if(sum > 0) {
end --;
} else {
begin ++;
}
}
}
}
return res;
}
}
public List<List