一个方法团灭 nSum 问题 :: labuladong的算法小抄

[labuladong]

文章链接点这里：一个方法团灭 nSum 问题

评论礼仪 见这里，违者直接拉黑。

[Gibson-Wan]

打卡

[MrChenyyds]

这题我想了很久，可以用回溯来做但是老是超时，回溯的框架哪里算是退出呢，按理说，当目标数为3且大于0时是不是就可以跳出循环，就是不知道在哪里跳出

[caobojia]

不能啊 我用的也是回溯 但是不超时 不过leetcode显示耗时2039ms

[YEthYuan]

Java版nSum模板及4Sum调用示例：

public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return nSum(nums, 4, 0, target);
    }

private List<List<Integer>> nSum(int[] nums, int n, int start, int target) {
    int len = nums.length;
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (n < 2 || len < n)
        return res;
    if (n == 2) {
        int small = start, big = len - 1;
        while (small < big) {
            int left = nums[small], right = nums[big];
            int sum = left + right;
            if (sum == target) {
                res.add(new ArrayList<Integer>(Arrays.asList(left, right)));
                while (small < big && nums[small] == left)
                    small++;
                while (small < big && nums[big] == right)
                    big--;
            } else if (sum > target) {
                while (small < big && nums[big] == right)
                    big--;
            } else if (sum < target) {
                while (small < big && nums[small] == left)
                    small++;
            }
        }
    } else {
        int i = start;
        while (i < len) {
            int now = nums[i];
            List<List<Integer>> sub = nSum(nums, n - 1, i + 1, target - now);
            for (List<Integer> s : sub) {
                s.add(now);
                res.add(s);
            }
            while (i < len && nums[i] == now)
                i++;
        }
    }
    return res;
}

[yuanfangluo]

需要把target的int改成long

[cheng-miao]

打卡

[zhubaohuabupt]

我也用暴力回溯的，当子序列长度大于3的时候退出，也是超时．
这个题目有点像组合二，不同的是，组合要求输出等于目标和的子序列长度不限制．当限制长度后，nSum 就成了组合二的一个子问题，用回溯有些浪费，即使剪支了，复杂度感觉也是高，所以感觉系统不让用回溯法？

[labuladong]

回溯这种暴力算法肯定可以，但是否利用了排序的便利减少不必要的计算？你们可以把代码贴出来看看。

[caobojia]

    List<List<Integer>> res;
    LinkedList<Integer> track;

    long trackNum;
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        trackNum = 0;
        res = new LinkedList<>();
        track = new LinkedList<>();
        help(nums, target, 0);
        return res;
    }

    private void help(int[] nums, int target, int start) {
        if(track.size() == 4){
           if(trackNum == target){
               res.add(new LinkedList<>(track));
           }
        }else{
            for(int i = start; i < nums.length; i ++){
                if(i > start && nums[i] == nums[i - 1]){
                    continue;
                }
                track.add(nums[i]);
                trackNum = trackNum + nums[i];
                help(nums, target, i + 1);
                track.removeLast();
                trackNum = trackNum - nums[i];
            }
        }
    }

[MrChenyyds]

我也是剪枝了退出还是超时

class Solution {
    public int traceroad(LinkedList<Integer> trace,int[] nums,boolean[] used,int i,int target){
        if(target<0)
             return 1;
        if(trace.size()==3){
            if(target==0){
                res.add(new LinkedList(trace));
                return 1;
            }
            return 0;
        }
        for(int j=i;j<nums.length;j++){
            if(j>0&&nums[j]==nums[j-1] &&!used[j-1]) continue;
            trace.add(nums[j]);
            target-=nums[j];
            used[j]=true;
            // System.out.println(trace);
            if(trace.getFirst()>0){
               return 0;
            }
            int t=traceroad(trace,nums,used,j+1,target);
            used[j]=false;
            target+=nums[j];
            trace.removeLast();
            if(t>0) return 0;
        }
        return 0;
    }

    List<List<Integer>>  res=new LinkedList<>();
    public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            LinkedList<Integer> trace = new LinkedList<>();
            boolean[] used=new boolean[nums.length];
            Arrays.fill(used,false);
            traceroad(trace,nums,used,0,0);
            return res;
    }
}

[zhao-zihan]

Java解法建议看第18题4Sum官方答案，里面加了平均数判断，可以避免极端案例中有负数或整数溢出的问题，如nums = [1000000000,1000000000,1000000000,1000000000] target = -294967296。这是官方新加的一个十分巧妙的edge case，上面YEthYuan同学提供的java版本会无法通过，原因是会在循环到n == 2即运算two sum时负数target会不断相减并反向溢出来到20亿整，会刚好与后两位和相等并返回，但负的target怎么可能从只有正整数的数组中获得呢，所以很有必要加上官方答案中的平均数判断来避免此问题，具体如下：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return kSum(nums, target, 0, 4);
    }
	
    public List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
        List<List<Integer>> res = new ArrayList<>();

        // If we have run out of numbers to add, return res.
        if (start == nums.length) {
            return res;
        }
        
        // There are k remaining values to add to the sum. The 
        // average of these values is at least target / k.
        int average_value = target / k;
        
        // We cannot obtain a sum of target if the smallest value
        // in nums is greater than target / k or if the largest 
        // value in nums is smaller than target / k.
        if  (nums[start] > average_value || average_value > nums[nums.length - 1]) {
            return res;
        }
        
        if (k == 2) {
            return twoSum(nums, target, start);
        }
    
        for (int i = start; i < nums.length; ++i) {
            if (i == start || nums[i - 1] != nums[i]) {
                for (List<Integer> subset : kSum(nums, target - nums[i], i + 1, k - 1)) {
                    res.add(new ArrayList<>(Arrays.asList(nums[i])));
                    res.get(res.size() - 1).addAll(subset);
                }
            }
        }
    
        return res;
    }
	
    public List<List<Integer>> twoSum(int[] nums, int target, int start) {
        List<List<Integer>> res = new ArrayList<>();
        int lo = start, hi = nums.length - 1;
    
        while (lo < hi) {
            int currSum = nums[lo] + nums[hi];
            if (currSum < target || (lo > start && nums[lo] == nums[lo - 1])) {
                ++lo;
            } else if (currSum > target || (hi < nums.length - 1 && nums[hi] == nums[hi + 1])) {
                --hi;
            } else {
                res.add(Arrays.asList(nums[lo++], nums[hi--]));
            }
        }
                                                          
        return res;
    }
}

[labuladong]

最简单的改法，把通用函数 nSumTarget 签名中的 int target 改成 long target 就可以了

[zhao-zihan]

更新，4sum官方又新加了一个test case，这次官方自己的答案都过不了了哈哈，不过很好解决，只需要在递归循环中再加一次平均数检测就行，我把自己发在英文区leetcode的评论贴过来了，详细的解释请看下面：

June 21, 2022, the official solution failed the newly added test case [-1000000000,-1000000000,1000000000,-1000000000,-1000000000] target = 294967296.

More specifically the average value test at the front of the algorithm is not sufficient enough to rule out all edge cases. In the above case, notice that the middle element is a positive one billion, which won't trigger the average value test after the initial sorting, and the rest four negative billions would add up to the target value due to java int number underflow.

A simple solution would be testing each subset in the res list before returning the final result, and we can do this in the recursive for loop. The process is quite easy since all the sublists are returned in non-decreasing order, so we can borrow the code from the average value test. This is an O(1) time complexity operation, so it barely affects the overall efficiency of the algorithm.

        for (int i = start; i < nums.length; ++i) {
            if (i == start || nums[i - 1] != nums[i]) {
                for (List<Integer> subset : kSum(nums, target - nums[i], i + 1, k - 1)) {
                    res.add(new ArrayList<>(Arrays.asList(nums[i])));
                    List<Integer> sub = res.get(res.size() - 1);
                    sub.addAll(subset);
                    if (sub.get(0) > target / k || target / k > sub.get(sub.size() - 1)) //insert average value test here
                        return new ArrayList<>();
                }
            }
        }

BTW I'm curious about if leetcode is using machine learning or some hack that I am not aware of for creating new test cases? It seems that many new test cases precede answer revisions.

full code:

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return kSum(nums, target, 0, 4);
    }
	
    public List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
        List<List<Integer>> res = new ArrayList<>();

        if (start == nums.length) {
            return res;
        }
        
        //the average value test that I was referring to
        int average_value = target / k;
        
        if  (nums[start] > average_value || average_value > nums[nums.length - 1]) {
            return res;
        }
        
        if (k == 2) {
            return twoSum(nums, target, start);
        }
    
        for (int i = start; i < nums.length; ++i) {
            if (i == start || nums[i - 1] != nums[i]) {
                for (List<Integer> subset : kSum(nums, target - nums[i], i + 1, k - 1)) {
                    res.add(new ArrayList<>(Arrays.asList(nums[i])));
                    List<Integer> sub = res.get(res.size() - 1);
                    sub.addAll(subset);
                    if (sub.get(0) > target / k || target / k > sub.get(sub.size() - 1)) //insert average value test here
                        return new ArrayList<>();
                }
            }
        }
    
        return res;
    }
	
    public List<List<Integer>> twoSum(int[] nums, int target, int start) {
        List<List<Integer>> res = new ArrayList<>();
        int lo = start, hi = nums.length - 1;
    
        while (lo < hi) {
            int currSum = nums[lo] + nums[hi];
            if (currSum < target || (lo > start && nums[lo] == nums[lo - 1])) {
                ++lo;
            } else if (currSum > target || (hi < nums.length - 1 && nums[hi] == nums[hi + 1])) {
                --hi;
            } else {
                res.add(Arrays.asList(nums[lo++], nums[hi--]));
            }
        }
                                                          
        return res;
    }
}

[nuo1nuo]

nSumTarget()里面得把target改成long类型，不然会有用例超出int范围

[gaozhanting]

// Swift代码： 回溯 子集 限层

import Foundation

class Solution {
    var res: [[Int]] = []
    var track: [Int] = []
    
    func threeSum(_ nums: [Int]) -> [[Int]] {
        backtrack(nums, 0, 0)
        return res
    }
    
    func backtrack(_ nums: [Int], _ start: Int, _ level: Int) {
        if level >= 4 { // 限制长度，只到第四层
            return
        }
        
        print("track: \(track)")
        
        if track.count == 3 && track[0] + track[1] + track[2] == 0 {
            res.append(track)
        }
        
        var i = start
        while (i < nums.count) {
            track.append(nums[i])
            backtrack(nums, i + 1, level + 1)
            track.removeLast()
            i += 1
        }
    }
}

let sample = [-1,0,1,2,-1,-4]
for arr in Solution().threeSum(sample) {
    print(arr)
}

[tadanokerako]

如果题目要求返回索引，但是经过排序索引发生了变化呀，这个问题怎么解决呢

[zhangpanzhan]

这时候，要么你依然使用leetcode 1的hashmap技巧，要么你就只能排序的时候，记录排序后的index和原来的index之间的对应关系；（通常可能需要你自己写排序）

[labuladong]

@tadanokerako 这是个好问题。一般来说的方法是用一个二元组把值和原始索引关联起来，这样无论值的位置怎么变，都可以找到最初的原始索引。可以参考 归并排序应用 和 田忌赛马问题。

[LeeHaruYa]

滴滴滴打卡

[GreakJack]

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        return nSum(nums, (long)target, 4, 0);
    }

    List<List<Integer>> nSum(int[] nums, long target, int n, int start) {
        List<List<Integer>> res = new ArrayList<>();

        if (n < 2 || nums.length < n) {
            return res;
        }

        if (n == 2) {
            int left = start, right = nums.length - 1;
            while (left < right) {
                int leftVal = nums[left];
                int rightVal = nums[right];
                long sum = leftVal + rightVal;
                if (sum < target) {
                    while (left < right && nums[left] == leftVal) left++;
                } else if (sum > target) {
                    while (left < right && nums[right] == rightVal) right--;
                } else if (sum == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);

                    while (left < right && nums[left] == leftVal)  left++;
                    while (left < right && nums[right] == rightVal) right--;
                }
            }
        } else {
            for (int i = start; i < nums.length; ++i) {
                List<List<Integer>> lists = nSum(nums, target - nums[i], n - 1, i + 1);
                for (List<Integer> list : lists) {
                    list.add(nums[i]);
                    res.add(list);
                }

                while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }
        }

        return res;
    }

巧用long，解决Java溢出问题

[zhangpanzhan]

else分支里的for循环不对。不能用for，要用while，因为内部的while 会让i跳到不重复的数字上，如果你for的话，i就不会跳了。

[yonggui-yan]

微信里面搜nsum好用。另一个等了半天没有出现。
厉害了！
每一层中，第一个元素不可重复！
剪掉了横向重复的枝！

[lixiaodao1234]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 暴力解法
        vector<int> arr;
        for(int i = 0; i < nums.size();i++){
            for(int j = i + 1; j < nums.size();j++){
                if(target == nums[i] + nums[j]){
                    arr.push_back(i);
                    arr.push_back(j);
                }
            }
        }
        return arr;
    }
};

暴力法

[lzp0717]

找出符合 a = b + 2c 的 3 个数。这种要求的，可以用这种思路解么？

[yuanjunfang]

我第一感觉是把他看做twosum，把sum=left+right改成sum=left+2*right这样，不知道对不对

[zhangpanzhan]

你可以创建新数组，前一部分是原来的nums， 后一部分是2*nums的部分，然后while left<right改成while left<right and left<n/2 and right>n/2; 这里的n是新数组的长度。

[max870701]

15題 3Sum Python版本1

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        print(nums)
        res = []
        l = len(nums)
        for i in range(l):
            # targe = 0
            print(nums[i])
            tuples = self.twoSum(nums, i+1, 0 - nums[i])
            print(tuples)
            for t in tuples:
                #nums[i].append(t)
                tmp = [nums[i]] + t
                if tmp not in res:
                    res.append([nums[i]] + t)
            while i < l-1 and nums[i] == nums[i+1]:
                i += 1
        return res


    def twoSum(self, nums, start,  target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        res = []
        left, right = start, len(nums) - 1
        
        while left < right:
            #left_num, right_num = nums[left], nums[right]
            #sum_num = left_num + right_num
            sum_num = nums[left] + nums[right]
            left_num, right_num = nums[left], nums[right]
            if sum_num < target:
                while (left < right) and (nums[left] == left_num):
                    left += 1
            elif sum_num > target:
                while (left < right) and (nums[right] == right_num):
                    right -= 1
            else: # sum_num == target
                res.append([left_num, right_num])
                while (left < right) and (nums[left] == left_num):
                    left += 1
                while (left < right) and (nums[right] == right_num):
                    right -= 1
        return res

Python版本2

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        for i in range(len(nums)):
            if nums[i] > 0:
                break
            if i == 0 or nums[i-1] != nums[i]:
                self.twoSum(nums, i, res)

        return res

    
    def twoSum(self, nums, i, res):
        lo = i + 1
        hi = len(nums) - 1
        while lo < hi:
            sumThree = nums[i] + nums[lo] + nums[hi]
            if sumThree < 0:
                lo += 1
            elif sumThree > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo-1]:
                    lo += 1

[bruceeewong]

20221229 打卡

[yqian442]

python 的nsum方法好像没能排重

[TimGuo8]

在递归之前去重就行 而不是之后 虽然不太清楚为什么python会这样

[ChenZeBin]

力扣是要求是返回下标，如果先对nums进行排序，那么没法返回下标了，这种情况怎么解，大佬。

[HJ520134]

力扣是要求是返回下标，如果先对nums进行排序，那么没法返回下标了，题解中都是返回的数组的值并非下标，这种情况怎么处理，指导下勒...

[garryzhong]

这个不就是子集问题吗