LeetCode 18.四数之和Java代码错误排查：大整数溢出问题

题目描述 #

给定整数数组nums，返回所有满足以下条件的唯一四元组[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]]

提交的Java代码 #

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

错误原因：整数溢出 #

Java中int类型的取值范围是[-2147483648, 2147483647]。测试用例里四个1000000000相加的结果是4000000000，远超出int的最大值，发生整数溢出后结果刚好等于-294967296（与给定target值一致），导致代码误判四数之和符合条件。

具体问题出在两处：

1. 初始边界判断：4 * nums[0] > target和4 * nums[nums.length - 1] < target，当nums[0]为1000000000时，4*1000000000溢出为-294967296，此时-294967296 > -294967296不成立，跳过了提前返回空数组的逻辑。
2. 求和判断：计算targetSum以及后续nums[left]+nums[right]的过程中，同样存在溢出，导致错误匹配。

修复方案 #

将所有涉及求和的计算转为long类型，避免溢出：

1. 边界判断改为：

   if (nums.length < 4 || (long)4 * nums[0] > target || (long)4 * nums[nums.length - 1] < target){
       return new ArrayList<>();
   }
   

2. 计算目标和与当前和时用long：

   long targetSum = (long)target - nums[i] - nums[j];
   while(left<right){
       long currentSum = (long)nums[left] + nums[right];
       if(currentSum == targetSum){
           // 原逻辑不变
       } else if(currentSum < targetSum){
           left++;
       } else {
           right--;
       }
   }
   

内容的提问来源于stack exchange，提问作者ADNAN HABIB