Leetcode 4sum 挑战输出错误

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

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

示例1：

输入：

nums = [1,0,-1,0,-2,2]

、

target = 0

输出：

[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

限制：

• 1 <= nums.length <= 200

• -109 <= nums[i] <= 109

• -109 <= target <= 109

这是我的代码：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int n = nums.length;

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int low = j + 1;
                int high = n - 1;
                int tsum = target - (nums[i] + nums[j]);
                while (low < high) {
                    if (tsum == nums[low] + nums[high]) {
                        List<Integer> tans = Arrays.asList(nums[i], nums[j], nums[low],nums[high];
                        ans.add(tans);
                        while (low < high && nums[low] == nums[low + 1]) {
                            low++;
                        }
                        while (low < high && nums[high] == nums[high - 1]) {
                            high--;
                        }
                        low++;
                        high--;
                    } else if (tsum > nums[low] + nums[high]) {
                        low++;
                    } else {
                        high--;
                    }
                }
            }
        }
        return ans;
    }
}

我的代码给出了案例 291 的错误输出（共 297 个案例）：

输入：

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

预期回报值：

[]

我的代码返回：

[[1000000000,1000000000,1000000000,1000000000]]

我检查了我的代码，但没有发现任何问题。我试运行代码，我的答案似乎是正确的。但是LeetCode平台告诉我输出是错误的。

我的错误是什么？

Answer 1

问题是

int

的范围。在有问题的测试用例中，您可以看到 1000000000+1000000000+1000000000+1000000000 的总和超过 2³¹−1，因此它回绕到 -294967296，这恰好是目标。结果你的程序给出了误报。

解决方案很简单：在对

long

值求和时使用

int

。对于仅对两个

nums

值求和，没有问题，因为代码挑战表明这些单独值的绝对值最多为 10⁹，并且该值的两倍仍在

int

的范围内。但是包含三个这样的项的和可能会导致 int 溢出。所以：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int n = nums.length;

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int low = j + 1;
                int high = n - 1;
                // Use long for calculating the sum:
                long tsum = (long) target - (nums[i] + nums[j]);
                while (low < high) {
                    if (tsum == nums[low] + nums[high]) {
                        List<Integer> tans = Arrays.asList(nums[i], nums[j], nums[low],nums[high]);
                        ans.add(tans);
                        while (low < high && nums[low] == nums[low + 1]) {
                            low++;
                        }
                        while (low < high && nums[high] == nums[high - 1]) {
                            high--;
                        }
                        low++;
                        high--;
                    } else if (tsum > nums[low] + nums[high]) {
                        low++;
                    } else {
                        high--;
                    }
                }
            }
        }
        return ans;
    }
}