Java中解决ArrayList两数和匹配时Long类型溢出问题

哈哈，这个溢出坑我踩过！你的双指针思路没问题，但核心问题是long加法溢出会导致比较逻辑完全错乱——比如两个超大正数相加变负数，代码会误以为和比elem小，错误移动左指针；两个极小负数相加变正数，又会误以为和比elem大，错误移动右指针。下面给你两种靠谱的修改方案：

方案一：用JDK内置方法捕获溢出（简洁易维护） #

利用Math.addExact()方法，它会在加法溢出时抛出ArithmeticException，我们可以通过捕获异常来判断溢出场景，进而修正比较逻辑：

public static boolean searchSum(ArrayList<Long> array, long elem) {
    int left = 0, right = array.size() - 1;
    while (left < right) {
        long n1 = array.get(left);
        long n2 = array.get(right);
        
        long sum;
        try {
            // 尝试安全相加，溢出则抛出异常
            sum = Math.addExact(n1, n2);
        } catch (ArithmeticException e) {
            // 处理溢出情况：
            if (n1 > 0 && n2 > 0) {
                // 两个正数相加溢出，实际和远大于Long.MAX_VALUE，必然大于elem（elem是long类型）
                sum = Long.MAX_VALUE + 1; // 标记为比最大值大的虚拟值
            } else {
                // 两个负数相加溢出，实际和远小于Long.MIN_VALUE，必然小于elem
                sum = Long.MIN_VALUE - 1; // 标记为比最小值小的虚拟值
            }
        }
        
        if (sum == elem) {
            return true;
        } else if (sum < elem) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

方案说明： #

• Math.addExact()是JDK8+提供的安全加法方法，溢出时主动抛异常，避免静默错误。
• 溢出场景下，根据两数正负就能判断实际和的范围：正数溢出的和肯定比任何long类型的elem大，负数溢出的和肯定比任何long类型的elem小，用虚拟值标记后就能正常驱动双指针移动。

方案二：纯逻辑判断（无异常，适合对异常敏感的场景） #

如果不想用异常处理，可以通过分情况判断，用减法替代加法，从根源避免溢出：

public static boolean searchSum(ArrayList<Long> array, long elem) {
    int left = 0, right = array.size() - 1;
    while (left < right) {
        long n1 = array.get(left);
        long n2 = array.get(right);
        
        // 用减法判断是否相等，避免加法溢出
        if (n1 == elem - n2) {
            return true;
        }
        
        // 分情况判断 n1 + n2 < elem，避免直接加法
        boolean sumLessThanElem;
        if (n2 > 0) {
            // n2是正数：若elem < n1，两正数相加必然大于elem；否则安全计算elem-n1再比较
            sumLessThanElem = elem >= n1 && n2 < elem - n1;
        } else if (n2 < 0) {
            // n2是负数：若elem > n1，两负数相加必然小于elem；否则安全计算elem-n1再比较
            sumLessThanElem = elem > n1 || n2 < elem - n1;
        } else {
            // n2是0，直接比较n1和elem
            sumLessThanElem = n1 < elem;
        }
        
        if (sumLessThanElem) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

方案说明： #

• 判断相等时用n1 == elem - n2：如果elem - n2溢出，说明n1 + n2的数学和不可能等于elem（因为elem是long类型，溢出后的结果不是正确的和），所以不会误判。
• 判断大小时分正负场景：利用有序数组的特性（n1 <= n2），通过减法替代加法，避免溢出风险，同时保证逻辑正确。

注意事项： #

两种方案都基于数组是升序排列的前提（双指针法本身就要求数组有序），如果你的数组是无序的，需要先调用Collections.sort(array)排序，或者改用哈希表法（哈希表法也需要处理溢出，但逻辑类似）。

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