leetcode18 四数之和 双指针

题目链接

代码：（时间复杂度为O(N^3)）

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        List<List<Integer>> result = new LinkedList<>();
        if(len < 4) return result;
        int a = 0, b = 1, c = 2, d = len - 1;
        long sum = getSum(nums,a,b,c,d);
        for (; a <= d - 3;){
            for (d= len - 1;d - 3 >= a; ){
                b = a + 1;
                c = d - 1;
                while(a <b &&c<d && b < c){
                    sum = getSum(nums,a,b,c,d);
                    if (sum == target){
                        result.add(Arrays.asList(nums[a],nums[b],nums[c],nums[d]));
                        b++;
                        while(b < len && nums[b] == nums[b - 1]) b++;
                        c--;
                        while(c - 1 > -1 && nums[c] == nums[c + 1]) c--;
                    }else if(sum < target){
                        b++;
                        while(b != c && nums[b] == nums[b - 1]) b++;
                    }else{
                        c--;
                        while(b != c && nums[c] == nums[c + 1]) c--;
                    }
                }
                d--;
                while(c < d && nums[d] == nums[d + 1]) d--;
            }
            d = len - 1;
            b = d - 1;
            a++;
            while(a < b && nums[a] == nums[a - 1]) a++;
        }

        return result;
    }

    public long getSum(final int[] arr,int a,int b,int c,int d){
        long result = 0L + arr[a] + arr[b] + arr[c] + arr[d];
        return result;
    }
}
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