?
3Sum
?
?
?
来自 <https://leetcode.com/problems/3sum/>
?
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:
?
?
??? For example, given array S = {-1 0 1 2 -1 -4},
?
A solution set is:
??? (-1, 0, 1)
??? (-1, -1, 2)
?
题目解读：
?
给定一个长度为n的整行数组S，其中存在三个元素a,b,c，使a+b+c=0. 找出所有的unique triplets使他们的和为0.
?
注解：
?
?
例如，对于数组S = {-1 0 1 2 -1 -4},
?
它的结果集为：
?
(-1, 0, 1)
(-1, -1, 2)
?
?
?
解析：
?
解法一：
?
暴力破解：利用三个循环，首先用i记录第一个数组元素，再用j记录第i+1个数组元素，在用k=j+1;记录第j+1数组元素，依次找到nums[i] + nums[j] + nums[k] == 0的三元组元素。时间复杂度高O(n3)
?
?
?
解法二：
?
首先对数组进行升序排序，使用快排时间复杂度为O(nlogn). 使用两个循环，
?
先升序排序，然后用第一重for循环确定第一个数字。
?
然后在第二重循环里，第二、第三个数字分别从两端往中间扫。
?
如果三个数的sum等于0，得到一组解。
?
如果三个数的sum小于0，说明需要增大，所以第二个数往右移。
?
如果三个数的sum大于0，说明需要减小，所以第三个数往左移。
?
时间复杂度：O(n2)
?
?
?
来自 <http://www.cnblogs.com/ganganloveu/p/3832180.html>
?
?
?
解法一代码：（Time Limit Exceeded）
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> sumList = new ArrayList<List<Integer>>();
if (nums.length < 3)
return sumList;
for (int i = 0; i < nums.length; i++) {
while((i < nums.length) && (nums[i]==nums[i+1])){
i++;
continue;
}
for (int j = i + 1; j < nums.length; j++) {
for (int k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> temp = new ArrayList<Integer>();
temp.add(nums[i]);
temp.add(nums[j]);
temp.add(nums[k]);
sumList.add(temp);
}
while((k < nums.length) && (nums[k]==nums[k+1]))
k++;
}
while((j < nums.length) && (nums[j]==nums[j+1]))
j++;
}
}
return sumList;
}
?
?
解法二代码:
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> sumList = new ArrayList<List<Integer>>();
if(nums.length < 3)
return sumList;
Arrays.sort(nums);
for(int i=0; i<nums.length-2; i++) {
if (i == 0 || nums[i] > nums[i - 1]) {
int start = i+1;
int end = nums.length-1;
while(start<end) {
if(nums[i]+nums[start]+nums[end] == 0) {
ArrayList<Integer> tempList = new ArrayList<Integer>();
tempList.add(nums[i]);
tempList.add(nums[start]);
tempList.add(nums[end]);
sumList.add(tempList);
start++;
end--;
//去掉重复的数据
while((start<end) && (nums[end]==nums[end+1]))
end--;
while((start<end) && (nums[start]==nums[start-1]))
start++;
} else if(nums[i]+nums[start]+nums[end] > 0) {
end--;
} else {
start++;
}
}
}
}
return sumList;
}
}
?
?
解法二性能
?
?
?
?
原文：http://972459637-qq-com.iteye.com/blog/2238517