龙

哇咔咔

0%

LeetCode 18.4Sum

发表于 更新于 分类于 Disqus：
求四个数的和。

18.4Sum

Description:

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

example:

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:

[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

题目理解：与3Sum一个意思。

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
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int m = nums.length;
        for ( int idx1 = 0, bound1 = m - 3 ; idx1 < bound1 && nums[idx1] * 4 <= target ;  ) {
            int target3 = target - nums[idx1];
            for ( int i = idx1 + 1, bound = m - 2 ; i < bound && nums[i] * 3 <= target3; ) {
                int l = i + 1, r = m - 1, sum = target3 - nums[i];
                if ( sum <= nums[r] * 2 && sum >= nums[l] * 2 ) {
                    while ( l < r ) {
                        int temp_sum = nums[l] + nums[r];
                        if ( temp_sum < sum ) l++; 
                        else if ( temp_sum > sum ) r--; 
                        else {
                            List<Integer> item = new ArrayList<>();
                            item.add(nums[idx1]);item.add(nums[i]);item.add(nums[l]);item.add(nums[r]);
                            result.add(item);
                            l++;
                            while ( l < r && nums[l] == nums[l-1] ) l++;
                            r--;
                            while ( l < r && nums[r] == nums[r+1] ) r--;
                        } 
                    }
                }
                i++;
                while ( i < bound && nums[i] == nums[i-1] ) i++;
            }
            idx1++;
            while ( idx1 < bound1 && nums[idx1] == nums[idx1-1] ) idx1++;
        }
        return result;
    }
}

内部包装了一个3Sum，但是其中一些中断的条件很重要，能够提升不少性能。

复杂度：n^3, 运行时间：28ms。

image

代码2：

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if ( nums.length < 4 ) return result;
        Arrays.sort(nums); 
        int[] ynums = new int[nums.length];
        int repeat = 1, idx = 1;
        ynums[0] = nums[0];
        for ( int i = 1; i < nums.length; i++ ) {
            if ( nums[i] == nums[i-1] ) {
                repeat++;
            } else {
                repeat = 1;
            }
            if ( repeat < 4 ) {
                ynums[idx++] = nums[i]; 
            } else if ( repeat == 4 && nums[i]*4 == target ) {
                myAdd( result, nums[i], nums[i], nums[i], nums[i]);
            }
        }

        int m = idx, ts_i = 0;
        int[][] two_sum = new int[m*(m-1)/2][3];
        for ( int i = 0; i < m - 1; i++ ) {
            repeat = 1;
            while ( i < m - 1 && ynums[i + 1] == ynums[i] ) {
                i++;
                repeat++;
            }
            if ( repeat == 2 ) {
                two_sum[ts_i][0] = ynums[i] * 2;
                two_sum[ts_i][1] = i - 1;
                two_sum[ts_i][2] = i;
                ts_i++;
            } else if ( repeat == 3 ) {
                two_sum[ts_i][0] = ynums[i] * 2;
                two_sum[ts_i][1] = i - 1;
                two_sum[ts_i][2] = i - 1;
                ts_i++;
            }
            for ( int j = i + 1; j < m;  ) {
                two_sum[ts_i][0] = ynums[i] + ynums[j];
                two_sum[ts_i][1] = i;
                two_sum[ts_i][2] = j;
                ts_i++;
                j++;
                while ( j < m && ynums[j] == ynums[j-1] ) {
                   j++;
                }
            }
        }
        Arrays.sort(two_sum, 0, ts_i, new MyCompare());
        int l = 0, r = ts_i - 1;
        while ( l < r ) {
            int sum = two_sum[l][0] + two_sum[r][0];
            if ( sum < target ) {
                l++;
            } else if ( sum > target ) {
                r--;
            } else {

                if ( two_sum[l][2] < two_sum[r][1] ) {
                    myAdd( result, ynums[two_sum[l][1]], ynums[two_sum[l][2]], ynums[two_sum[r][1]], ynums[two_sum[r][2]]);
                }

                int ll = l + 1, rr = r - 1;
                while ( ll < r && two_sum[ll][0] == two_sum[ll-1][0] ) {
                    if ( two_sum[ll][2] < two_sum[r][1] ) {
                        myAdd( result, ynums[two_sum[ll][1]], ynums[two_sum[ll][2]], ynums[two_sum[r][1]], ynums[two_sum[r][2]]);
                    }
                    ll++;
                }
                while ( ll < rr && two_sum[rr][0] == two_sum[rr+1][0] ) {
                    if ( two_sum[rr][1] > two_sum[l][2] ) {
                        myAdd( result, ynums[two_sum[l][1]], ynums[two_sum[l][2]], ynums[two_sum[rr][1]], ynums[two_sum[rr][2]]);
                    }
                    rr--;
                }

                l++; r--;
            }
        }
        return result;
    }

    private void myAdd( List<List<Integer>> result, int a1, int a2, int b1, int b2) {
        List<Integer> item = new ArrayList<>();
        item.add(a1); item.add(a2);
        item.add(b1); item.add(b2);
        result.add(item); 
    }

    private class MyCompare implements Comparator<int[]> {
        public int compare(int[] o1, int[] o2) {
            if ( o1[0] > o2[0] ) {
                return 1;
            } else if ( o1[0] < o2[0] ) {
                return -1;
            } else {
                if ( o1[1] < o2[1] ) {
                    return -1;
                } else if ( o1[1] > o2[1] ) {
                    return 1;
                } else {
                    if ( o1[2] < o2[2] ) {
                        return -1;
                    } else {
                        return 1;
                    }
                }
            }
        }
    }
}

贼复杂，想法到是很简单，就是先计算两两数的和，然后就变成了类似2Sum的东西，但是其中的多种重复情况，使得编写程序十分复杂。

并且代码还可以优化，但是懒得想了，就不该开始这个代码(；′⌒`)。

复杂度：n^2log(n)(个人简单估计是这样的，但是常数因子很大，而且占用空间很多)。

运行时间：85ms。

image