【LeetCode.18】4Sum （C++、Python3）

淡淡的烟草味﹌ 2022-04-25 05:12 166阅读 0赞

# 问题描述 #

> Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.  
> The solution set must not contain duplicate quadruplets.

必须明白，各个四元组不能重复，但四元组中是可以使用重复元素的。

# 示例 #

> Given array nums = \[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\]  
> \]

从示例来看，每个四元组是排序的，虽然题面上没有明说。下面的程序是能保证排序的。

# N-SUM C++代码 #

思路及代码来自于[Python 140ms beats 100%, and works for N-sum (N>=2)][Python 140ms beats 100_ and works for N-sum _N_2]。有些地方我略作优化。

> The core is to implement a fast 2-pointer to solve 2-sum, and recursion to reduce the N-sum to 2-sum. Some optimization was be made knowing the list is sorted.

中心思想就是把N-sum问题分治成2-sum，再2-sum双向扫描法解决2-sum问题（[【LeetCode.15】3Sum][LeetCode.15_3Sum]就是使用的这种方法）。

class Solution { 
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) { 
            sort(nums.begin(), nums.end());//排序
            return NSum(nums, 4, 0, nums.size()-1, target);//注意传入的是最大索引
            
        }
        
        vector<vector<int>> NSum(vector<int>& nums, int N, int start, int end, int target) { 
            vector<vector<int>> results;
            if(end - start + 1 < N || nums[start]*N > target || nums[end] * N < target){ 
                return results;
            }
            if(N == 2){ 
                return twoSum(nums, start, end, target);
            }
            for(int i = start; i < end-N+2; i++){ 
                int select = nums[i];//确定了当前N元祖的第一个元素
                if(i == start || nums[i] != nums[i-1]){ 
                    vector<vector<int>> result = NSum(nums, N-1, i+1, end, target-select);
                    for(auto res: result){ 
                        res.insert(res.begin(),select);
                        results.push_back(res);
                    }
                }
            }
            return results;
        }
        
        vector<vector<int>> twoSum(vector<int>& nums, int start, int end, int target) { 
            vector<vector<int>> result;
            while(start < end){ 
                if(nums[start] + nums[end] == target){ 
                    result.push_back({ nums[start], nums[end]});
                    while(start < end && nums[start+1] == nums[start]){ start++;}
                    while(start < end && nums[end-1] == nums[end]){ end--;}
                    start++; end--;
                }
                else if(nums[start] + nums[end] < target){ 
                    start++;
                }
                else{ 
                    end--;
                }
            }
            return result;
        }
    };

1.  `fourSum`函数是调用的主函数，主要用来指定N为4；`NSum`函数才是真正起作用的函数，递归，将Nsum问题进行分治，直到分治为2sum问题；`twoSum`函数是用来处理2sum问题。PS：学过归并排序的都有所了解这种思想吧。
2.  注意最初传给`NSum`函数的end是数组的最大索引；且end在递归传值中从来没有变过。
3.  `NSum`函数是递归函数，每次执行的函数体的任务是负责找到从start到end索引之间有N个数的和等于target。每次函数都会创建一个局部的二维vector，最终返回一个二维vector。
4.  递归分为过程和终点。过程即为那个for循环，注意循环的检查条件是`i < end-N+2`，即`i< end-(N-2)`，即`i<= end-(N-1)`，这样当N>2时i最大会到达倒数第N个索引，这样就能留出刚好足够的空位。比如当N=3，且i已经到达倒数第3个索引时，这里就会刚好留出两个空位，最终问题会分治成2sum问题，所以至少要留两个空位。当然你写成`i <= end`也能通过，但会造成又多几次循环走到返回空二维vector的递归终点去。
5.  继续分析递归过程。select确定了当前N元祖的第一个元素，然后if去重，这里去重意思不是要N元组中没有重复元素，而是，当前N元祖的第一个元素的某种情况分析完后，所以其他重复情况就不用分析了。然后调用自身，将问题进行分治。在子for循环中，将返回的二维vector添加上之前确定了的第一个元素。
6.  `res.insert(res.begin(),select);`这句可以保证最终返回的4元祖都是排好序的元素，但改成`res.push_back(select);`也能通过，但4元祖里面的元素就不是排好序的了，会变成\[c, d, b, a\]。（这说明程序里面并没有要求4元祖是排好序的）
7.  接下来是递归终点。首先是`if(N == 2)`这个终点，将2sum问题交给`twoSum`函数处理；然后是`if(end - start + 1 < N || nums[start]*N > target || nums[end] * N < target)`这个终点，当遇到不可能的情况时，返回空的vector（返回到上层函数时，子for循环不会执行，因为其中么有元素），情况分别是：1.当前范围不足N个元素 2.最小情况都大于目标 3.最大情况都小于目标（你需要想到数组是排过序的）。
8.  总之，对于NSUM问题，先找到N-2个元素都是谁（这里其实算是穷举的，`if(i == start || nums[i] != nums[i-1])`这里的去重只是防止了重复的分析，但连续重复元素会从第一个重复元素开始一直分治递归下去），剩下2个元素交给`twoSum`函数寻找。

![在这里插入图片描述][2019050520411557.jpg]  
截图用来解释第5点，当代码没有if去重时，代码会出现重复分析的情况（两次循环体都使得第二个位置为0）；可见正常情况下，第二个位置是0的情况，程序只会分析一次，只是在之后双向扫描时，有两种可能性，分别是\[-3,0,0,-3\]和\[-3,0,1,2\]。

# N-SUM Python3代码 #

class Solution:
        def fourSum(self, nums, target):
            nums.sort()
            results = []
            self.findNsum(nums, target, 4, [], results)
            return results
    
        def findNsum(self, nums, target, N, result, results):
            if len(nums) < N or N < 2: return
    
            # solve 2-sum
            if N == 2:
                l,r = 0,len(nums)-1
                while l < r:
                    if nums[l] + nums[r] == target:
                        results.append(result + [nums[l], nums[r]])
                        l += 1
                        r -= 1
                        while l < r and nums[l] == nums[l - 1]:
                            l += 1
                        while r > l and nums[r] == nums[r + 1]:
                            r -= 1
                    elif nums[l] + nums[r] < target:
                        l += 1
                    else:
                        r -= 1
            else:
                for i in range(0, len(nums)-N+1):   # careful about range
                    if target < nums[i]*N or target > nums[-1]*N:  # take advantages of sorted list
                        break
                    if i == 0 or i > 0 and nums[i-1] != nums[i]:  # recursively reduce N
                        self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
            return

整体框架和c++代码差不多，就简单说几个注意事项吧

1.  递归过程的range是`len(nums)-N+1`，它和c++那里是一样的，即`(len(nums)-1)+N+2`。
2.  生成数组的过程不一样，c++代码是到达递归终点才逐层返回，才开始添加数组元素；但py代码是从递归过程的每一层就开始添加数组元素了（在`result+[nums[i]]`处，说明每次调用递归都会生成新的list），但只有当分治成2sum问题解决后才会添加到二维数组`results`中（`results.append(result + [nums[l], nums[r]])`处，到达此处说明`if nums[l] + nums[r] == target:`判断通过）。
3.  `nums[i+1:]`处，每次给递归函数的，不是索引范围，而是新分片出来的子list。
4.  处理2sum问题时它没有单独拎出来作为一个函数。
5.  `if len(nums) < N or N < 2: return`处表示不可能的情况，但我认为不可能进入这个if，1.空位每次都是留够了的，所以`len(nums) < N`不可能进入；2.N每次递归减1，到2了就到了递归终点，所以`N < 2`不可能进入。

class Solution:
        def fourSum(self, nums, target):
            def findNsum(nums, target, N, result, results):
                if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N:  # early termination
                    return
                if N == 2: # two pointers solve sorted 2-sum problem
                    l,r = 0,len(nums)-1
                    while l < r:
                        s = nums[l] + nums[r]
                        if s == target:
                            results.append(result + [nums[l], nums[r]])
                            l += 1
                            r -= 1
                            while l < r and nums[l] == nums[l - 1]:
                                l += 1
                            while r > l and nums[r] == nums[r + 1]:
                                r -= 1
                        elif s < target:
                            l += 1
                        else:
                            r -= 1
                else: # recursively reduce N
                    for i in range(len(nums)-N+1):
                        if i == 0 or (i > 0 and nums[i-1] != nums[i]):
                            findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
    
            results = []
            findNsum(sorted(nums), target, 4, [], results)
            return results

整合了上一个版本，将递归函数写成内部函数调用。

class Solution:
        def fourSum(self, nums, target):
            def findNsum(l, r, target, N, result, results):
                if r-l+1 < N or N < 2 or target < nums[l]*N or target > nums[r]*N:  # early termination
                    return
                if N == 2: # two pointers solve sorted 2-sum problem
                    while l < r:
                        s = nums[l] + nums[r]
                        if s == target:
                            results.append(result + [nums[l], nums[r]])
                            l += 1
                            r -= 1
                            while l < r and nums[l] == nums[l - 1]:
                                l += 1
                            while r > l and nums[r] == nums[r + 1]:
                                r -= 1
                        elif s < target:
                            l += 1
                        else:
                            r -= 1
                else: # recursively reduce N
                    for i in range(l, r+1):
                        if i == l or (i > l and nums[i-1] != nums[i]):
                            findNsum(i+1, r, target-nums[i], N-1, result+[nums[i]], results)
    
            nums.sort()
            results = []
            findNsum(0, len(nums)-1, target, 4, [], results)
            return results

和上一个版本的区别在于，每次传递给函数的搜索范围，不是每次新分片的list，而是传递两个索引作为搜索范围。

# Fastest C++ Submission——8ms #

class Solution { 
    public:
        vector<vector<int>> fourSum(vector<int> nums, int target) 
        { 
            if (nums.size() < 4) return{ };
    
            sort(nums.begin(), nums.end());
            vector<vector<int>> output;
            
            for (size_t i = 0; i < nums.size() - 3; i++)
            { 
                if (i != 0 && nums[i] == nums[i - 1]) continue;
                if (target < (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3])) break;
                if (target >(nums[i] + nums[nums.size() - 1] + nums[nums.size() - 2] + nums[nums.size() - 3])) continue;
    
                for (size_t j = i + 1; j < nums.size() - 2; j++)
                { 
                    if (j != i + 1 && nums[j] == nums[j - 1]) continue;
                    if (target < (nums[i] + nums[j] + nums[j + 1] + nums[j + 2])) break;
                    if (target >(nums[i] + nums[j] + nums[nums.size() - 1] + nums[nums.size() - 2])) continue;
    
                    size_t front = j + 1;
                    size_t back = nums.size() - 1;
                    int sum = target - nums[i] - nums[j];
                    while (front < back)
                    { 
                        if (nums[front] + nums[back] == sum)
                        { 
                            output.push_back({  nums[i], nums[j], nums[front], nums[back] });
                            while ((front < back) && nums[front] == nums[front + 1]) front++;
                            while ((back < front) && nums[front] == nums[back - 1]) back--;
                            front++; back--;
                        }
                        else if (nums[front] + nums[back] < sum) front++;
                        else back--;
                    }
                    //while ((j < nums.size() - 2) && nums[j] == nums[j + 1]) j++;
                }
    
                //while ((i < nums.size() - 3) && nums[i] == nums[i + 1]) i++;
            }
            
            return output;
        }
    };

1.  简单粗暴，只处理4sum问题，先用两个for循环确定前两个元素，再用双向扫描法确定剩余两个元素。
2.  `if (target < (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3])) break;`和`if (target >(nums[i] + nums[nums.size() - 1] + nums[nums.size() - 2] + nums[nums.size() - 3])) continue;`才是最精确的判断来判断不可能的情况啊。之前是用最前或最后元素\*N来判断的。
3.  注释了两行我认为不需要的代码，也能通过。

[Python 140ms beats 100_ and works for N-sum _N_2]: https://leetcode.com/problems/4sum/discuss/8545/Python-140ms-beats-100-and-works-for-N-sum-%28Ngreater2%29
[LeetCode.15_3Sum]: https://blog.csdn.net/anlian523/article/details/89715310
[2019050520411557.jpg]: /images/20220210/59e925efcb454ea7b22cd1618c7cf1f8.png