【LeedCode】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: 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] ]

分析：

暴力法，三层for循环，时间复杂度为O(n^3)，，这显然不是一种好的解决方式

我的做法是先对数组进行排序，这样负数在排在前面（负数越小，则它的绝对值越大），0在中间（如果存在0），正数在后面。排序算法的时间复杂度是O(nlgn)

然后从左往右取负数，从右往左取正数。即从两边向中间扫描。两个数求和的情况则刚好可以两边各取一个数进行判断，对于三个数求和的情况，我们可以先确定一个数，然后再去两个数的和为第一个取出的数的相反数即可。

注：当数组长度小于3时，直接返回null

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

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

        int len = num.length;

        if(num==null || len<3){

            return null;

        }

        Arrays.sort(num);

        for(int i =0;i<len-2;i++){

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

                continue;

            }

            int j = i+1;

            int k = len-1;

            int target = -num[i];

            while(j<k){

                if(num[j]+num[k]==target){

                    result.add(Arrays.asList(num[i],num[j],num[k]));

                    j++;

                    k--;

                    while(j<k && num[j]==num[j-1]){

                        j++;

                    }

                    while(j>k && num[k]==num[k+1]){

                        k--;

                    }

                }else if(num[j]+num[k]>target){

                    k--;

                }else{

                    j++;

                }

            }

        }

        return result;

    }

巴特西

【LeedCode】3Sum

最新文章

热门文章