Java：解决long求和溢出问题及2000万元素两数之和查找

Great question! Dealing with integer overflow when checking pair sums is a common pitfall, especially with large datasets like 20 million elements. Let's break down why your current approach fails and walk through practical, efficient solutions.

问题根源 #

当两个long值相加超出Long.MAX_VALUE（9223372036854775807）或低于Long.MIN_VALUE（-9223372036854775808）时，会触发整数溢出，结果会按照补码规则循环到相反符号的数值。比如Long.MAX_VALUE + 1会变成Long.MIN_VALUE，这直接导致你判断sum == target时出现逻辑错误。

解决方案一：无溢出的数学判断法（推荐，性能最优） #

核心思路：避免直接计算x + y，而是通过符号判断和变形条件来验证是否存在符合条件的y，同时利用HashSet将查找复杂度从O(n)降到O(1)。

关键观察 #

只有同号的两个long相加才会溢出：

• 两个正数相加溢出→结果为负数，但正数之和不可能等于负数目标值，这种情况直接排除。
• 两个负数相加溢出→结果为正数，但负数之和不可能等于正数目标值，这种情况也直接排除。
• 异号数值相加不会溢出（结果绝对值必然小于其中较大的数的绝对值），可以直接判断。

实现步骤 #

1. 先将ArrayList<Long>转换为几个集合，优化后续查找：

   • HashSet<Long> positives：存储所有大于0的数值
   • HashSet<Long> negatives：存储所有小于0的数值
   • boolean hasZero：标记集合中是否包含0
   • （可选）HashMultiset<Long> countSet：如果需要处理重复元素（比如同一个数值出现多次），用Guava的HashMultiset记录每个数值的出现次数。

2. 遍历每个元素x，根据x的符号和目标值target的关系，分情况判断：

import java.util.ArrayList;
import java.util.HashSet;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.Multiset;

public class PairSumFinder {
    public static boolean hasPairWithSum(ArrayList<Long> nums, long target) {
        HashSet<Long> positives = new HashSet<>();
        HashSet<Long> negatives = new HashSet<>();
        boolean hasZero = false;
        Multiset<Long> countSet = HashMultiset.create();

        // 初始化集合
        for (long num : nums) {
            countSet.add(num);
            if (num > 0) {
                positives.add(num);
            } else if (num < 0) {
                negatives.add(num);
            } else {
                hasZero = true;
            }
        }

        for (long x : nums) {
            long y = target - x;

            // 处理x为0的情况
            if (x == 0) {
                if (target == 0) {
                    // 需要至少两个0，或者允许同一个元素重复使用（根据需求调整）
                    return countSet.count(0) >= 2;
                }
                continue;
            }

            // 处理x为正数的情况
            if (x > 0) {
                if (y > 0) {
                    // 两个正数相加，若target<=0则不可能满足（溢出结果为负，正数和不可能为负）
                    if (target <= 0) continue;
                    // 无溢出，直接检查positives中是否存在y，且处理重复元素
                    if (x == y) {
                        return countSet.count(x) >= 2;
                    } else {
                        return positives.contains(y);
                    }
                } else if (y == 0) {
                    return hasZero && target == x;
                } else {
                    // x正y负，无溢出，检查negatives
                    return negatives.contains(y);
                }
            }

            // 处理x为负数的情况
            if (x < 0) {
                if (y < 0) {
                    // 两个负数相加，若target>=0则不可能满足（溢出结果为正，负数和不可能为正）
                    if (target >= 0) continue;
                    // 无溢出，检查negatives中是否存在y，处理重复元素
                    if (x == y) {
                        return countSet.count(x) >= 2;
                    } else {
                        return negatives.contains(y);
                    }
                } else if (y == 0) {
                    return hasZero && target == x;
                } else {
                    // x负y正，无溢出，检查positives
                    return positives.contains(y);
                }
            }
        }
        return false;
    }
}

解决方案二：使用BigInteger避免溢出（简单但性能稍差） #

如果不想处理复杂的符号判断，可以将所有long转换为BigInteger，利用其支持任意大小整数的特性来计算和判断。缺点是BigInteger的内存占用和运算速度比原生long慢，但对于2000万元素的规模，只要内存足够，仍然可行。

实现示例 #

import java.util.ArrayList;
import java.util.HashSet;
import java.math.BigInteger;

public class BigIntegerPairSumFinder {
    public static boolean hasPairWithSum(ArrayList<Long> nums, long target) {
        HashSet<BigInteger> numSet = new HashSet<>();
        BigInteger targetBig = BigInteger.valueOf(target);

        for (long num : nums) {
            numSet.add(BigInteger.valueOf(num));
        }

        for (long num : nums) {
            BigInteger numBig = BigInteger.valueOf(num);
            BigInteger needed = targetBig.subtract(numBig);
            if (numSet.contains(needed)) {
                // 处理重复元素的情况
                if (numBig.equals(needed)) {
                    // 检查是否至少出现两次
                    int count = 0;
                    for (long n : nums) {
                        if (n == num) {
                            count++;
                            if (count >=2) return true;
                        }
                    }
                } else {
                    return true;
                }
            }
        }
        return false;
    }
}

性能优化提示 #

• 优先使用方案一，原生long的运算和查找速度远快于BigInteger。
• 转换ArrayList到HashSet只需要一次O(n)遍历，后续查找都是O(1)，整体时间复杂度为O(n)，适合2000万级别的数据。
• 如果内存紧张，可以不用单独分正负集合，直接用一个HashSet<Long>，但需要在判断时加入符号检查逻辑。

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