4-sum 问题：我的代码选择四个正整数，而 sum 目标是负数

Question

我正在尝试解决LeetCode问题18。 4总和:

给定一个由

nums

整数组成的数组

n

，返回 所有 唯一四元组

[nums[a], nums[b], nums[c], nums[d]]

的数组，使得：

• 0 <= a, b, c, d < n

• a

  、

  b

  、

  c

  和

  d

  不同。

• nums[a] + nums[b] + nums[c] + nums[d] == target

您可以按任意顺序返回答案。

问题

虽然我设法通过了几个测试用例，但对于以下输入，我的代码返回了错误的答案：

输入：

nums = [1000000000,1000000000,1000000000,1000000000]
target = -294967296

预期输出：

[]

我的代码产生的输出：

[[1000000000,1000000000,1000000000,1000000000]]

我的代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> quadriplets = new ArrayList<>();
        
        if (nums.length < 4 || 4 * nums[0] > target || 4 * nums[nums.length - 1] < target){
            return new ArrayList<>();
        }
        for(int i=0;i<=nums.length-4;i++){
            if(i==0 || nums[i] != nums[i-1]){
                for(int j=i+1;j<=nums.length-3;j++ ){
                    if(j==i+1 || nums[j] !=nums[j-1]){
                        int left=j+1 ,right=nums.length-1;
                        int targetSum=target-nums[i]-nums[j];
                        while(left<right){
                            if(nums[left]+nums[right]==targetSum){
                                List<Integer> quadt= new ArrayList<>();
                                quadt.add(nums[i]);
                                quadt.add(nums[j]);
                                quadt.add(nums[left]);
                                quadt.add(nums[right]);
                                quadriplets.add(quadt);
                                while(left<nums.length-1 && nums[left]==nums[left+1])left++;
                                while(right>0 && nums[right]==nums[right-1]) right--;
                                left++;
                                right--;
                            }
                            else if(nums[left]+nums[right] < targetSum){
                                left++;
                            }else{
                                right--;
                            }
                        }
                    }
                }
            }
        }
        return quadriplets;
    }
}

问题

我不明白为什么这段代码会生成该输出。我的错误在哪里？

Answer 1

您遇到的问题是由整数溢出引起的。对于示例测试用例，表达式

target-nums[i]-nums[j]

将计算为正数，即使

target

为负数并且

nums[i]

和

nums[j]

为正数。一个快速的解决方案是转换为

long

:

long targetSum=(long)target-nums[i]-nums[j];

这将解决测试用例失败的问题。但测试用例较多，下面的表达式也可能发生溢出：

4 * nums[0] > target || 4 * nums[nums.length - 1] < target

您可以使用

4L

而不是

4

来解决此问题：

4L * nums[0] > target || 4L * nums[nums.length - 1] < target

这个更正后的实现将通过所有测试。