3Sum——leetcode

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)

public class Solution {

    public List<List<Integer>> threeSum(int[] num) {

        Set<List<Integer>> set=new HashSet<List<Integer>>();

        Arrays.sort(num);

        List<List<Integer>> ans=new ArrayList<List<Integer>>();

        if(num.length<=2)

        {

            return ans;

        }

        for(int i=0;i<num.length-2;i++)

        {

            if(i>0&&num[i]==num[i-1])

            {

                continue;

            }

            int j=i+1;

            int k=num.length-1;//j,k双指针，巧妙降低复杂度至N^2

            while(j<k)

            {

                int sum=num[i]+num[j]+num[k];

                if(sum==0)

                {

                    List<Integer> list=new ArrayList<Integer>();

                    list.add(num[i]);

                    list.add(num[j]);

                    list.add(num[k]);

                    set.add(list);

                    j++;k--;

                }

                else if(sum<0)

                {

                    j++;

                }

                else

                {

                    k--;

                }

            }

        }

        ans.addAll(set);//这个函数不错，可以把set中的元素全都添加到List。List的函数addAll(<Collection>)

        return ans;

    }

}

巴特西

3Sum——leetcode

最新文章

热门文章