LeetCode 3sum

链接: https://oj.leetcode.com/problems/3sum/

2sum:尺取法 通过a+b与target比较,.根据大于或小于不断缩小范围

3sum:即对0~n个数分别做2sum...

去重:

if(i!=0&&num[i]==num[i-1])
				continue;

只有当i==0或者当前的数!=上一个数时才继续计算2sum

下面简单说明一下:

       当前数为num[i]时,则需要在num[i+1~n]中找到一个2sum==-num[i];      但是因为num[i]==num[i-1],该2sum肯定会被case2中,重复                             //case1

       当前数为num[i-1]时,需要在num[i~n]中找到一个2sum==-num[i-1];,                                                                                                                                        //case2

 当时只这样判断去重是不行的.测试数据:

-2,0,0,2,2

还需要加上

if(!ans.contains(tans))

完整代码:

public class Solution
{
	public List<List<Integer>> threeSum(int[] num )
	{
		List<Integer> tans=new ArrayList<Integer>();
		List<List<Integer>> ans=new ArrayList<List<Integer>>();
		Arrays.sort(num);
		for(int i=0;i<num.length-2;i++)
		{
			int l=i+1,r=num.length-1;
			if(i!=0&&num[i]==num[i-1])
				continue;
			while(l<r)		
			{
				if(num[l]+num[r]+num[i]==0)
				{
					tans.add(new Integer(num[i]));
					tans.add(new Integer(num[l]));
					tans.add(new Integer(num[r]));
					if(!ans.contains(tans))
					{
					    ans.add(new ArrayList<Integer>(tans));
					}
					tans.clear();
					l++;
					r--;
				}
				else if(num[l]+num[r]+num[i]<0)
				{
					l++;	
				}
				else
				{
					r--;
				}

			}
		}
		return ans;
	}
}