LeetCode-3Sum

3Sum

##题目

####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)

##解题思路
该题是求解在一个有重复数字的数组中是否存在三个数的和为0的问题。这道题是Two Sum的扩展。当然，如果我们采用“暴搜”，时间复杂度则为O(n^3)。但是由于这道题中存在重复的元素，因此采用哈希表的解法不是很方便，因此，这里通过首先将数组进行排序，然后采用左右夹逼的方法。总的时间复杂度为O(n^2+nlogn)=(n^2),空间复杂度是O(n)。

这里将Two Sum作为3Sum的一个subroutine来处理，不过具体实现需要注意更多的细节,尤其是需要考虑过滤重复元素的问题。

##算法代码
代码采用JAVA实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {
	//利用2sum可以求解，由于可能存在重复元素，所以采用散列表会有冲突，这里采用左右夹逼来求解2sum,整个时间复杂度为O(n^2+nlogn)=O(n^2)
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
    	ArrayList<ArrayList<Integer>> lists=new ArrayList<ArrayList<Integer>>();
        if(num.length<=2) return lists;
        Arrays.sort(num);
		for(int i=0;i<num.length-2;i++)
		{
		    if(i>0&&num[i]==num[i-1]) //考虑重复问题，保证lists中没有重复
				continue;
		    if(num[i]<=0)
			    tweSum(lists,num,i,num[i],-num[i]);
		}   
		return lists;     
    }

    public void tweSum(ArrayList<ArrayList<Integer>> lists,int[] num,int start,int term,int target)
    {
        int i=start+1;
    	int j=num.length-1;

    	while(i<j)
    	{
    		if((num[i]+num[j])==target)
    		{
    			ArrayList<Integer> list=new ArrayList<Integer>();
    			list.add(term);
    			list.add(num[i]);
    			list.add(num[j]);
    			lists.add(list);
    			i++;
    			j--;
    			while(i<j&&num[i]==num[i-1])  //考虑重复问题
                    i++;  
                while(i<j&&num[j]==num[j+1])  //考虑重复问题
                    j--;  
    		}else if((num[i]+num[j])>target)
    		{
    			j--;
    		}else
    			i++;
    	}
    }
}

Comments

▲