Java如何不使用嵌套循环判断有序数组中是否存在符合目标和的数对

实现思路 #

由于输入数组已经预先按升序排序，我们可以用双指针法实现需求，完全避免嵌套循环，仅用到基础的变量、循环、分支语法，时间复杂度为O(n)，比原有O(n²)的嵌套循环方案效率提升明显：

• 初始化左指针指向数组首个元素（下标为0），右指针指向数组末尾元素（下标为arr.length - 1）
• 只要左指针下标小于右指针下标，就持续进行判断：
  • 计算两个指针指向元素的和
  • 若和等于目标值key，直接返回true，说明存在符合要求的数对
  • 若和小于key，说明当前总和偏小，需要更大的求和值，将左指针向右移动一位
  • 若和大于key，说明当前总和偏大，需要更小的求和值，将右指针向左移动一位
• 遍历结束后仍未找到匹配的数对，返回false

修改后完整可运行代码 #

import java.util.*;

class Tuple {
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.print("Enter the number of distinct elements in sorted array: ");
    int size = sc.nextInt();
    System.out.print("Enter " +size+ " elements: ");
    int[] arr = new int[size];
    for (int i = 0; i<size; i++) {
      arr[i]=sc.nextInt();
    }
    System.out.print("Enter key: ");
    int key = sc.nextInt();
    if (checkTuple(arr, key)) {
      System.out.println("Exist");
    } else {
      System.out.println("Not exist");
    }
  }
  
  // 方法返回值：存在和为key的整数对返回true，否则返回false
  public static boolean checkTuple(int[] arr, int key) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == key) {
            return true;
        } else if (sum < key) {
            left++;
        } else {
            right--;
        }
    }
    return false;
  }
}

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