algo/di-ling-zh-bfe1b/yi-ge-fang-894da/

[giscus[bot]]

algo/di-ling-zh-bfe1b/yi-ge-fang-894da/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！第 21 期打卡挑战 (https://opedk.xet.tech/s/4ptSo2) 最后一天报名！ 读完本文，你不仅学会了算法套路，还可以顺便解决...

https://labuladong.github.io/algo/di-ling-zh-bfe1b/yi-ge-fang-894da/

[ZeplerFu]

4Sum问题力扣的测试用例加了几个会导致原代码无法通过，比如
测试用例:[1000000000,1000000000,1000000000,1000000000]
-294967296
测试结果:[[1000000000,1000000000,1000000000,1000000000]]
期望结果:[]
是因为target – nums[i]负向超出了int的数值范围，会从int最大值重新开始计算，继续往下递归。相当于4个1000000000两两抵消了，最后结果与-294967296还是相等。
此时只需要把nSumTarget传入的参数target的数据类型从int改为long即可通过全部用例。

[ChenxiZhang168]

Java 测试了 tuple.add(nums[i]); for each loop 会报错

[SkyeKD]

因为Arrays.asList(left,right)新建的数组后面不能用add修改。用new ArrayList<>(Arrays.asList(left,right))

[BreezAm]

return new int[]{nums[lo], nums[hi]};不是返回下标吗？

[llxblhyvia]

python3在解决3sum时仍然会出现重复答案，因为由于语言特性，在while循环内部对i进行增量之后，假如此时i = 2，跳到外面的大循环for i in range(len(nums))时,外层认为i还是应该为2，没有进行实际的跳过，所以这里外层也要用while.....i+=1手动增量。

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        n = len(nums)
        i = 0
        while i < n:
            firstNum = nums[i]
            target = 0 - firstNum
            tuples = self.twoSum(nums, i+1, target)
            for tuple in tuples:
                tuple.append(nums[i])
                print('tuple', tuple)
                res.append(tuple)
            while i < n - 1 and nums[i+1] == nums[i]:
                i += 1
            i += 1
        return res

[alizer]

是的，看到这里，也觉得奇怪，这其实是Python for循环 语言特性的差异，外层一旦确定for循环的逻辑，循环体内对 i 的修改，外层是无感的。
Java 不存在这个问题

[Sundw-818]

python3的nSum函数还是会出现重复的，下面对i的循环应改成while, 并且手动增加i, i += 1

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        return self.nSumTarget(nums, 4, 0, target)

    def nSumTarget(self, nums, n, start, target):
        sz = len(nums)
        res = []

        if n < 2 or sz < n:
            return res
        
        if n == 2:
            l, r = start, sz - 1
            while l < r:
                left, right = nums[l], nums[r]
                sum_ = left + right
                if sum_ < target:
                    l += 1
                elif sum_ > target:
                    r -= 1
                else:
                    res.append([left, right])
                    while l < r and nums[l] == left:
                        l += 1
                    while l < r and nums[r] == right:
                        r -= 1
        else:
            i = start
            while i < sz:
                sub = self.nSumTarget(nums, n - 1, i+1, target - nums[i])
                for arr in sub:
                    arr.append(nums[i])
                    res.append(arr)
                while i < sz - 1 and nums[i] == nums[i+1]:
                    i += 1
                i += 1
        return res

[tiandee]

有同学反馈，threeSum的题java代码执行不通过，这是因为twoSumTarget方法中这行代码导致的，List list = Arrays.asList(left, right); 这里返回的list是不可变list，在后面threeSumTarget中内层for循环中使用tuple.add(nums[i]);会报错。
可以使用List list = new ArrayList<>(Arrays.asList(left, right));
完整版代码如下

class Solution {

    public List<List<Integer>> twoSumTarget(int[] nums, int start, int target) {
      // 左指针改为从 start 开始，其他不变
      int lo = start, hi = nums.length - 1;
      List<List<Integer>> res = new ArrayList<>();
      while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // 记录索引 lo 和 hi 最初对应的值
        int left = nums[lo], right = nums[hi];
        if (sum < target)
          lo++;
        else if (sum > target)
          hi--;
        else {
          res.add(new ArrayList<>(Arrays.asList(left, right)));
          // 跳过所有重复的元素
          while (lo < hi && nums[lo] == left) lo++;
          while (lo < hi && nums[hi] == right) hi--;
        }
      }
      return res;
    }
    public List<List<Integer>> threeSum(int[] nums) {
      // 求和为 0 的三元组
      return threeSumTarget(nums, 0);
    }

    /* 计算数组 nums 中所有和为 target 的三元组 */
    public List<List<Integer>> threeSumTarget(int[] nums, int target) {
      // 数组得排个序
      Arrays.sort(nums);
      int n = nums.length;
      List<List<Integer>> res = new ArrayList<>();
      // 穷举 threeSum 的第一个数
      for (int i = 0; i < n; i++) {
        // 对 target - nums[i] 计算 twoSum
        List<List<Integer>> tuples =
            twoSumTarget(nums, i + 1, target - nums[i]);
        // 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
        for (List<Integer> tuple : tuples) {
          tuple.add(nums[i]);
          res.add(tuple);
        }
        // 跳过第一个数字重复的情况，否则会出现重复结果
        while (i < n - 1 && nums[i] == nums[i + 1]) i++;
      }
      return res;
    }
}

[tiandee]

力扣可运行

[karlli1976]

这篇文章很好地解释了Arrays.asList和new ArrayList(Arrays.asList())的不同，值得一读。

https://www.baeldung.com/java-arrays-aslist-vs-new-arraylist

在刷题时很多时候需要用到array和List的转换，这些基本概念一定要搞清楚。

[DreamYuki]

看完以后豁然开朗，谢谢博主带我领略到了算法世界的美妙

[shiboys]

大佬，膜拜！

[shiboys]

Java 版本的有 2 个bug：其中第一个其他版本也有，没有通过 leetcode 的测试用例，希望楼主改下

if (sum < target) {
                while (lo < hi && nums.get(lo) == left) lo++;
            } else if (sum > target) {
                while (lo < hi && nums.get(hi) == right) hi--;
            } else {
               // bug1: 这里如果一直 sum > target ，会导致 lo==hi, 但是这里的 left + right != sum。
              // 只是 lo==hi 这个因素导致逻辑走了这里，需要排除下这种情况。
             // bug2，也是这里，只是 java 特有，楼主如果使用了 Arrays.asList(..) 这个 api，返回的 List 是
            // 只读的，而你在下面又拿出这个列表添加元素，会导致异常
                res.add(Arrays.asList(left, right));
                while (lo < hi && nums.get(lo) == left) lo++;
                while (lo < hi && nums.get(hi) == right) hi--;
            }

[shiboys]

我上面列举的 bug1 是错误的，bug1 不存在，bug2 是存储的，其他兄弟也有回复提到的。之所以有些测试用例没有通过，是其他原因：
测试用例 nums= [1000000000,1000000000,1000000000,1000000000] ，target = -294967296
4Sum 会出现问题，原因是 int 溢出吧，导致 target - 2*nums[0] = 2000000000 ，把 target 类型改为long 就能修复。

[zjfjack]

ThreeSum这里真的有必要放这个么？

if (sum < target) {
    while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
    while (lo < hi && nums[hi] == right) hi--;

假设数字不相等，这里就得跑两遍，因为lo或者hi总是要加一次的，毕竟一开始 nums[lo] == left 和 nums[hi] == right。你不跑这个直接就进入下一个内循环了。

就算数字相等，你这里还是得多跑一遍，还是那个原因: 一开始nums[lo] == left 和 nums[hi] == right。

即便可以优化成避免第一次重复的情况

if (sum < target) {
    lo++;
    while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
    hi++;
    while (lo < hi && nums[hi] == right) hi--;

实际来说也没什么太大的意义，如果相同，这里比了2次+取1次值，进入下一个内循环也就是比1次+取两次值+一次加的操作，如果不相同，你就多了一轮。

总结来说优化后依然意义不大，而且代码看起来很乱。

[max870701]

nSum 問題的 Python3 解法

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        self.n = len(nums)
        return self.nSum(nums, 4, 0, target)
    
    # 給定 nums, n , start, target，返回 k 個數字的總和為 target 的所有 List[List[int]]
    def nSum(self, nums, k, start, target):
        res = []
        if k < 2 or self.n < k:
            return res
        
        # Base case 為 twoSum
        if k == 2:
            left, right = start, self.n - 1
            while left < right:
                s = nums[left] + nums[right]
                if s < target:
                    left += 1
                elif s > target:
                    right -= 1
                else:
                    res.append([nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
        else:
            # k > 2, 遞歸調用 (n-1)Sum
            for i in range(start, self.n):
                if i == start or (i > start and nums[i] != nums[i - 1]):
                    sub = self.nSum(nums, k - 1, i + 1, target - nums[i])
                    for arr in sub:
                        res.append([nums[i]] + arr)

        return res

[zhou-ziyan]

3Sum里“跳过第一个数字重复的情况，否则会出现重复结果” 感觉用while写更清楚，原本在每个for循环还要i++一次就很难思考。

        int i = 0;
        while (i < nums.size() - 2) {
            int init = nums[i];
            // do something
            // 跳过第一个数字重复的情况，否则会出现重复结果
            while (i < nums.size() && nums[i] == init) i++;
        }

[codezs09]

nSum问题是不是也可以看做组合/子集问题？ 即返回n个数的组合其sum正好为指定值时，就存到res里。套用 https://labuladong.github.io/algo/di-ling-zh-bfe1b/hui-su-sua-56e11/ 方法做？

[codezs09]

根据该思路测试了4sum 正常

class Solution {
public:
    vector<vector<int>> res; 
    vector<int> combo; 

    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end()); 
        backtrack(nums, target);
        return res; 
    }

    // let's say find all combinations of 4 numbers first
    void backtrack(vector<int> &nums, long target, int start=0) {
        // base case
        if (combo.size() == 4) {
            if (target == 0)
                res.push_back(combo); 
            return; 
        }

        for (int i = start; i < nums.size(); i++) {
            if (i > start && nums[i] == nums[i-1]) {
                continue;   // avoid repeitition
            }
            combo.push_back(nums[i]); 
            counts++; 
            backtrack(nums, target-nums[i], i+1); 
            // exit
            combo.pop_back();
            counts--; 
        }
    }
};