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

 

题意：在给出的数组中找出3个依次递增的值，使得它们相加结果为0。将每组值返回。

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

解题思路：先将数组排序，在遍历数组固定第一个数，找剩下两个数，使得其满足相加为0。

public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
		rank(num);
		List<List<Integer>> lists = new ArrayList<List<Integer>>();
//固定第一个数
		for(int i=0;i<num.length-2;i++)
		{
//第一个数都大于0，相加永远为正数
			if(num[i]>0) break;
//num[i]==num[i-1]说明在上一轮已经遍历过，再找就重复了。
			if(i>0&&num[i]==num[i-1])
				continue;
			int j=i+1;
			int k = num.length-1;
			List<Integer> list = new ArrayList<Integer>();
//遍历找出j和k的值
			while(j<k)
			{
				if(num[i]+num[j]+num[k]==0)
				{
//说明已经找过
					if(num[j]==num[j-1]&&j>i+1) 
					{
						j++;
						continue;
					}
					else
					{
						list.add(num[i]);
						list.add(num[j]);
						list.add(num[k]);
						lists.add(list);
						list = new ArrayList<Integer>();
						j++;
						continue;
					}
				}else if(num[i]+num[j]+num[k]>0)
				{
					k--;
					if(num[k]==num[k+1])
						k--;
					continue;
				}else
				{
					j++;
					if(num[j]==num[j-1])
						j++;
					continue;
				}
				
			}
		}
		return lists;
    }
	
	public void rank(int[] sum)
	{
		for(int i=0;i<sum.length-1;i++)
		{
			for(int j=i+1;j<sum.length;j++)
			{
				if(sum[i]>sum[j])
				{
					int temp = sum[i];
					sum[i]=sum[j];
					sum[j]=temp;
				}
			}
		}
	}
}