时间戳

首页 > 解决方案 > 有没有办法在不使用嵌套循环的情况下查找数组中是否存在特定总和？（爪哇）

java - 有没有办法在不使用嵌套循环的情况下查找数组中是否存在特定总和？（爪哇）

问题描述

所以这段代码有效，但我想知道如果我不想使用嵌套循环怎么办？如果我们能坚持基本原则，我们将不胜感激！呵呵：>

编辑：要输入的列表已经按升序排序，如果有帮助的话！

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");
    }
  }
  
  // method , returns true if there exists at least 1 pair of integers 
  //whose sum equals key, or false otherwise
  public static boolean checkTuple(int[] arr, int key) {
    int[] remainder = new int[arr.length];
    for (int i=0; i<arr.length; i++) {
      for (int j=0; j<arr.length; j++) {
        if (arr[i]+arr[j]==key) {
          return true;
        }
      }
    }
    return false;  
  }
}

标签： javaarraysnested-loops

解决方案

您可以使用以下方法来做到这一点。它只有一个循环。
输入arr参数必须按升序排序。
该算法依赖于数组已排序的事实。
最初，我们总结了数组的第一个和最后一个元素。如果我们想要的总和低于当前对的总和，在这种情况下，我们需要减少正确的索引。否则，如果期望的总和高于当前对的总和，在这种情况下，我们必须增加左索引。

因此，在最坏的情况下，我们只会遍历整个数组一次。因此，复杂度将是 O(n)

public static boolean checkTuple(int[] arr, int key) {
    int leftIndex = 0;
    int rightIndex = arr.length - 1;

    while (leftIndex < rightIndex) {
        int currentSum = arr[leftIndex] + arr[rightIndex];
        if (currentSum == key) {
            return true;
        }

        if (currentSum > key) {
            rightIndex--;
        } 
        if (currentSum < key) {
            leftIndex++;
        }
    }

    return false;
}

推荐阅读