Java中如何在ArrayList内查找两数之和等于指定Key？

嘿，你已经完成了最核心的准备工作——把数据读入集合，还把待查数字列表排好序了！接下来验证目标Key是否为列表中两数之和，双指针法是最适合你的方案，刚好适配已排序的列表，效率比暴力遍历或者反复二分查找高很多。

核心逻辑 #

因为列表已经是升序排列的，我们可以用两个指针分别从两端向中间移动：

• 左指针（left）从列表开头（索引0）出发，指向最小的元素
• 右指针（right）从列表末尾（索引size-1）出发，指向最大的元素
• 计算两指针指向元素的和，和目标Key对比：
  1. 如果和等于Key：直接找到符合条件的组合，返回true
  2. 如果和小于Key：左指针右移一位，找更大的元素来凑出更大的和
  3. 如果和大于Key：右指针左移一位，找更小的元素来凑出更小的和
  4. 重复上述步骤，直到left >= right（指针相遇，说明没有符合条件的组合）

代码实现（结合你的现有逻辑） #

首先写一个专门的方法来实现双指针判断：

private boolean isTwoSum(List<Integer> sortedArrList, int target) {
    int left = 0;
    int right = sortedArrList.size() - 1;
    
    while (left < right) { // 这里用left < right，避免同一个元素被重复使用
        int currentSum = sortedArrList.get(left) + sortedArrList.get(right);
        if (currentSum == target) {
            System.out.println("找到组合：" + sortedArrList.get(left) + " + " + sortedArrList.get(right) + " = " + target);
            return true;
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    System.out.println("未找到能组成 " + target + " 的两个元素");
    return false;
}

然后修改你现有case "-a"里的循环逻辑，替换掉原来的elementIsContained调用：

case "-a": 
    buffer.mergeSort(arrList, 0, arrList.size()-1); 
    for(int i=0; i < sums.size(); i++){
        // 调用新的双指针方法代替原逻辑
        isTwoSum(arrList, sums.get(i)); 
    } 
    break;

为什么这个方法比你之前的思路更优 #

你之前考虑用二分查找遍历组合，本质上是对每个元素num，查找target - num是否存在，时间复杂度是O(n log n)；而双指针法只需要一次遍历，时间复杂度是O(n)，效率更高。另外你提到的“排除大于Key的元素”，双指针法会自动处理——当右指针指向的元素加上左指针元素已经大于Key时，右指针左移，相当于自动跳过了过大的元素，不需要额外处理。

如果你的需求允许同一个元素被使用两次（比如列表中有元素5，目标Key是10），只需要把循环条件改成left <= right即可。

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