By

文章目录
  1. 1. 解法1
  2. 2. 解法2
  3. 3. 测试用例
  4. 4. 参考

leetcode地址：https://leetcode.com/problems/3sum/

Problem:
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)

解法1

最简单的暴力求解,O(N^3)，利用HashMap进行去重，加了一个剪枝方法，竟然也AC了，runtime：936ms

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public List<List<Integer>> threeSum(int[] num) {
	List<List<Integer>> ret=new ArrayList<List<Integer>>();
	
	HashMap<String,ThreeNum> coupleMap=new HashMap<String,ThreeNum>();
    int a,b,c,temp;
	boolean isCut=false;
    
    //sort the num list as asc
    for(int i=0;i<num.length;i++)
    {
        for(int j=i+1;j<num.length;j++)
        {
            if(num[i]>num[j])
            {
                temp=num[i];
                num[i]=num[j];
                num[j]=temp;
            }
        }
    }
    
    
    //a<=c<=b
    for(int i=0;i<num.length;i++)
    {
    	a=num[i];
        for(int j=num.length-1;j>i;j--)
        {
        	b=num[j];
        	isCut=false;
            for(int k=j-1;k>i;k--)
            {
            	c=num[k];
            	if(a+b+c==0)
            	{
            		ThreeNum threeNum=new ThreeNum(a,c,b);
            		if(!coupleMap.containsKey(threeNum.toString()))//check the couple whether is exist
            		{
            			coupleMap.put(threeNum.toString(), threeNum);
            			break;
            		}
            	}else if(a+b+c<0){
            		//we will cut it
            		isCut=true;
            		break;
            	}
            }
        }
    }
    
    for(String threeNumString:coupleMap.keySet())
    {
    	ArrayList<Integer> threeNumList=new ArrayList<Integer>();
    	threeNumList.add(coupleMap.get(threeNumString).a);
    	threeNumList.add(coupleMap.get(threeNumString).b);
    	threeNumList.add(coupleMap.get(threeNumString).c);
    	ret.add(threeNumList);
    }
    
    return ret;
}

class ThreeNum{
	public int a,b,c;
	
	public ThreeNum(int a,int b,int c)
	{
		this.a=a;
		this.b=b;
		this.c=c;
	}
	
	public String toString()
	{
		return a+","+b+","+c;
	}
}

解法2

       按照一维数组中2求两个数字之和的思路：复杂度为O(N^2),runtime:322ms

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public List<List<Integer>> threeSum(int[] num) {
	List<List<Integer>> ret=new ArrayList<List<Integer>>();
	
	int p,q,temp,sum;
	for(int i=0;i<num.length;i++)
    {
        for(int j=i+1;j<num.length;j++)
        {
            if(num[i]>num[j])
            {
                temp=num[i];
                num[i]=num[j];
                num[j]=temp;
            }
        }
    }
	
	for(int k=0;k<num.length-1;k++)
	{
		if(k>0 && num[k-1]==num[k])
			continue;//去重
		p=k+1;
		q=num.length-1;//初始化两端的指针
		
		while(p<q)
		{
			sum=num[k]+num[p]+num[q];
			if(p>k+1 && num[p]==num[p-1])
			{
				p++;
				continue;
			}
			
			if(q<num.length-1 && num[q]==num[q+1])
			{
				q--;
				continue;
			}
			
			
			if(sum<0)
			{
				//p指针向右
				p++;
			} else if(sum==0)
			{//求得解
				ret.add(Arrays.asList(num[k],num[p],num[q]));
				p++;
				q--;
			}else{
				q--;//q指针向左
			}
			
			
		}
	}
	
	
	
	return ret;
}

测试用例

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * test data,except data
 */
List<TestExample> testExampleList=new ArrayList<TestExample>();

@Before
public void before()
{
	this.testExampleList.add(new TestExample(new int[]{-1,0,1,2,-1,-4},Arrays.asList("-1,0,1","-1,-1,2")));
	this.testExampleList.add(new TestExample(new int[]{0,0,0,0},Arrays.asList("0,0,0")));
	this.testExampleList.add(new TestExample(new int[]{-1,1,-1,1},new ArrayList<String>()));
	this.testExampleList.add(new TestExample(new int[]{-2,0,1,1,2},Arrays.asList("-2,0,2","-2,1,1")));
}

@Test
public void testThreeSum1()
{
	ThreeSum threeSum=new ThreeSum();

	for(TestExample example:this.testExampleList)
	{
		List<List<Integer>> ret=threeSum.threeSum(example.testPara);
		int count=0;
		if(ret.size()==example.testExcept.size())
		{
			for(List list:ret)
			{
				if(example.testExcept.contains(join(list,",")))
				{
					count++;
				}else{
					break;
				}
			}
		}
		Assert.assertEquals(count, example.testExcept.size());
		
	}
	
}

@After
public void after()
{
	this.testExampleList.clear();
}

/**
 * 测试样例数据
 * @author Administrator
 *
 */
static class TestExample{
	public int[] testPara;
	public List<String> testExcept;
	
	public TestExample(int[] testPara,List<String> testExcept)
	{
		this.testPara=testPara;
		this.testExcept=testExcept;
	}
}

/**
 * join 操作
 * @param strList
 * @param split
 * @return
 */
public static String join(List<Integer> strList,String split){
    StringBuffer sb=new StringBuffer();
    for(int i=0;i<strList.size();i++){
         if(i==(strList.size()-1)){
             sb.append(strList.get(i));
         }else{
             sb.append(strList.get(i)).append(split);
         }
    }
    
    return new String(sb);
}

参考

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 解法1
  2. 2. 解法2
  3. 3. 测试用例
  4. 4. 参考