LeetCode-15-3Sum*

 

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:

 

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a≤b≤c)
• The solution set must not contain duplicate triplets.

 

    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.

 

注解：

 

• 三元组中的元素(a,b,c)一定是升序的。（例如，a≤b≤c）
• 结果集中不能包含重复的三元组。

 

例如，对于数组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;
    }
}

 

 

解法二性能