有没有一种方法可以不使用嵌套循环来确定数组中是否有特定的和？（爪哇）

Question

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

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

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;  
  }
}

Answer 1

不需要存储阵列。在读取元素时，只需检查是否有匹配的对。当然，你需要提前索要钥匙

import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Tuple {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.print("Enter the number of distinct elements: ");
    int size = sc.nextInt();
    System.out.print("Enter key: ");
    int key = sc.nextInt();
    System.out.print("Enter " + size + " elements: ");
    Set<Integer> set = new TreeSet<>();
    for (int i = 0; i < size; i++) {
      int value = sc.nextInt();
      if (arr.contains(key - value)) {
        System.out.println("Exist");
        return;
      }
      set.add(value);
    }
    System.out.println("Not exist");
  }
}

（我意识到这几乎肯定是一个家庭作业问题，目的不是找出一对是否存在，而是编写checkTuple方法，但如果目的仅仅是找出一对是否存在，这种方法既节省时间又节省空间。）

Answer 2

如果不允许一个数字使用两次，则需要创建一个映射，记录数组中每个数字的出现次数：

Map<Integer, Long> counts =
    IntStream.of(arr).boxed().collect(groupingBy(a -> a, Collectors.counting());

然后，循环浏览地图的关键点：

for (int key : counts.keySet()) {
  // You need key + otherKey == target.
  int otherKey = target - key;

  long otherCount = counts.getOrDefault(otherKey, 0L);

  // otherKey wasn't in the array.
  if (otherCount == 0) continue;

  // key and otherKey aren't equal, so you don't need two (or more) occurrences.
  if (key != otherKey) return true;

  // key and otherKey are equal, so you need two (or more) occurrences.
  if (otherCount >= 2) {
    return true;
  }
}

// Didn't find a match.
return false;

Answer 3

你可以用下面的方法来做。它只有一个循环
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;
}

Answer 4

是的，你可以在O(n)

static boolean sum2(int[] xs, int s) {
    Set<Integer> set = new HashSet<>();
    for (int x : xs)
        if (set.contains(s - x))    return true;
        else                        set.add(x);
    return false;
}

比如

int[] xs = new int[]{5, 5, 12, -7, 21};

System.out.println("====  all pairs should match ===");
for (int a = 0; a < xs.length; a++)
    for (int b = a + 1; b < xs.length; b++)
        System.out.println(sum2(xs, xs[a] + xs[b]));

System.out.println("==== false cases ===");
System.out.println(sum2(xs, 12 + 12));
System.out.println(sum2(xs, -5));

有输出

====  all pairs should match ===
true
true
true
true
true
true
true
true
true
true
==== false cases ===
false
false

Answer 5

我想指出的是，您没有在代码中使用余数数组。 你可以用这样的方法来代替这个方法

  public static boolean checkTuple(int[] arr, int key) {
        for (int i=0; i<arr.length; i++) {
                if (arr[i]+arr[i]==key) {
                    return true;
                }

        }
        return false;
    }

只需去掉for循环，将j更改为i