在 leetcode 中针对问题 18. 4sum 得到错误的输出

Question

我一直在练习leetcode上的搜索问题，我正在做4sum的问题，当我解决它时，代码在297个案例中的第291个案例中给出了错误的输出，当我重新检查我的代码时，我没有发现任何问题我试运行代码，我的答案是正确的，但 leetcode 给出了错误的输出。我已经很头疼了请帮助我

(4sum)问题是- 给定一个包含 n 个整数的数组 nums，返回所有唯一四元组 [nums[a], nums[b], nums[c], nums[d]] 的数组，使得：

0<= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.

这是我的代码

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;
    }
}

输入为 [1000000000,1000000000,1000000000,1000000000]，目标=-294967296

Answer 1

问题是

int

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

解决方案很简单：在对

long

值求和时使用

int

。仅将其中两个相加是没有问题的，因为代码挑战表明各个值的绝对值最多为 10⁹，并且该值的两倍仍在

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;
    }
}