leetcode14.4sum

发表于 更新于 分类于 ，

题目要求

此处为原题地址

1
2
3
4
5
6
7
8
9
10
11
12
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.

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]
]

也就是从数组中找到所有四个数字，这四个数字的和为目标值。这四个数字的组合不能重复。

这题的核心思路请参考我的另一篇博客three-sum，即如何找到三个数字，使其和为目标值。

思路一：直接利用three-sum

在three-sum的基础上在外围再加一圈循环，即在最左侧数字固定的情况下，寻找右侧数组中的three-sum结果。时间复杂度O(n3)。这里需要注意及时处理掉重复的情况。

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
public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int length = nums.length;
        if(length<4){
            return result;
        }
        Arrays.sort(nums);
        for(int i = 0 ; i < length-3 ; ){
            int firstValue = nums[i];
            
            //three sum
            for(int j = i+1 ; j < length-2 ; ){
                int secondValue = nums[j];
                int leftPointer = j+1;
                int rightPointer = length-1;
                while(leftPointer<rightPointer){
                    int currentSum = firstValue + secondValue + nums[leftPointer] + nums[rightPointer];
                    if(currentSum == target){
                        result.add(Arrays.asList(firstValue, secondValue, nums[leftPointer], nums[rightPointer]));
                    }
                    if(currentSum<=target){
                        while(nums[leftPointer]==nums[++leftPointer] && leftPointer<rightPointer);
                    }
                    if(currentSum>=target){
                        while(nums[rightPointer--]==nums[rightPointer] && leftPointer<rightPointer);
                    }
                }
                //去除重复情况
                while(nums[j] == nums[++j] && j < length - 2);
            }
            //去除重复情况
            while(nums[i] == nums[++i] && i < length - 3);
        }
        return result;
    }

提高算法的效率

在three-sum的基础上计算4sum不可避免的需要O(n3)的时间复杂度。那么就需要尽可能排除不可能的情况来提高计算效率。因为数组已经被排序，所以可以根据数组中元素的位置判断接下来的情况是否有可能合成目标值。

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
//思路二：不断的排除不可能的情况，以加快遍历，核心的还是3sum
public List<List<Integer>> fourSum2(int[] nums, int target) {
    ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
    int len = nums.length;
    if (nums == null || len < 4)
        return res;

    Arrays.sort(nums);

    int max = nums[len - 1];
    //
    if (4 * nums[0] > target || 4 * max < target)
        return res;

    int i, z;
    for (i = 0; i < len; i++) {
        z = nums[i];
        if (i > 0 && z == nums[i - 1])// avoid duplicate 防止重复
            continue;
        if (z + 3 * max < target) // z is too small 当前值即时加上最大值也不足以构成目标值，进入下一轮循环
            continue;
        if (4 * z > target) // z is too large 当前值*4都大于目标值，余下的值不可能再生成最大值
            break;
        if (4 * z == target) { // z is the boundary
            if (i + 3 < len && nums[i + 3] == z)
                res.add(Arrays.asList(z, z, z, z));
            break;
        }

        threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
    }

    return res;
}

/*
 * Find all possible distinguished three numbers adding up to the target
 * in sorted array nums[] between indices low and high. If there are,
 * add all of them into the ArrayList fourSumList, using
 * fourSumList.add(Arrays.asList(z1, the three numbers))
 */
public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
        int z1) {
    if (low + 1 >= high)
        return;

    int max = nums[high];
    if (3 * nums[low] > target || 3 * max < target)
        return;

    int i, z;
    for (i = low; i < high - 1; i++) {
        z = nums[i];
        if (i > low && z == nums[i - 1]) // avoid duplicate
            continue;
        if (z + 2 * max < target) // z is too small
            continue;

        if (3 * z > target) // z is too large
            break;

        if (3 * z == target) { // z is the boundary
            if (i + 1 < high && nums[i + 2] == z)
                fourSumList.add(Arrays.asList(z1, z, z, z));
            break;
        }

        twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
    }

}

/*
 * Find all possible distinguished two numbers adding up to the target
 * in sorted array nums[] between indices low and high. If there are,
 * add all of them into the ArrayList fourSumList, using
 * fourSumList.add(Arrays.asList(z1, z2, the two numbers))
 */
public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
        int z1, int z2) {

    if (low >= high)
        return;

    if (2 * nums[low] > target || 2 * nums[high] < target)
        return;

    int i = low, j = high, sum, x;
    while (i < j) {
        sum = nums[i] + nums[j];
        if (sum == target) {
            fourSumList.add(Arrays.asList(z1, z2, nums[i], nums[j]));

            x = nums[i];
            while (++i < j && x == nums[i]) // avoid duplicate
                ;
            x = nums[j];
            while (i < --j && x == nums[j]) // avoid duplicate
                ;
        }
        if (sum < target)
            i++;
        if (sum > target)
            j--;
    }
    return;
}