返回A和B中使得a + b <= c的所有配对(a,b)的总数。其中a来自A，b来自B。

Question

我在做一些练习时遇到了这个问题...

给定两个 int 数组 A 和 B，以及一个 int 变量 c，返回满足 a + b <= c 的所有 (a, b) 数对总数，其中 a 来自 A，b 来自 B。

我立刻想到了暴力解法，但是似乎无法想出更好的时间复杂度。我尝试先对数组进行排序，并尝试找到某种模式，但是没有任何进展。我考虑了一个数组包含负数的情况。在这种情况下，我不能只看 A 或 B 中是否有小于 c 的值，因为另一个数组中可能有一个负数，当它们相加时可以得到一个 <= c 的结果。如果您有任何见解、想法或线索，将不胜感激。

import java.util.*;

public class CountPairs {

    public static void main(String args[]){
        int arrayA[] = {32,45,9,4};
        int arrayB[] = {43,457,54,90};

        Scanner scan = new Scanner(System.in);

        System.out.println("Choose the value that you want to find pairs <= ");
        int c = scan.nextInt();

        System.out.println("The total number of pairs are : " + pairs(arrayA, arrayB, c));
    }

    public static int pairs(int A[], int B[], int n) {
        int count = 0;

        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int total = A[i] + B[j];

                if(total <= n)
                    count++;
            }
        }

        return count;
    }
}

- Elroy Jetson

---

请查看此链接：https://dev59.com/3W865IYBdhLWcg3wcOHG - root

谢谢，@root545，链接很有帮助。 - Elroy Jetson

我不能使用@Hulk，因为如果数组B有任何负值，我可能会错过满足条件的一对。考虑a = 10，c = 5。如果跳过像这样的内部循环，但是arrayB有一个值，例如b = -6，那么我们就会错过一对。 - Elroy Jetson

@ElroyJetson，你当然是正确的——我错过了可能会有负数的情况。 - Hulk

Answer 1

让我们花一秒钟来欣赏使用Javaslang和利用声明式函数方法时任务变得多么容易：

初始数据：

int arrayA[] = {32, 45, 9, 4};
int arrayB[] = {43, 457, 54, 90};

int c = 100;

解决方案:

int result = List.ofAll(arrayA)
  .crossProduct(List.ofAll(arrayB))
  .distinct()
  .count(t -> t._1 + t._2 <= c);

- Grzegorz Piwowarek

---

这个不行。Zip 只会创建相同索引的组合，而不是所有的组合。你需要使用 flatmap。 - Ulysse Mizrahi

@UlysseMizrahi 好观点 :) 确实需要组合。 - Grzegorz Piwowarek

Answer 2

如果您是出于练习的目的，我建议您完全忽略性能，而是注重代码的清晰度。通常情况下，开发人员会养成尽可能提高代码效率的习惯，而牺牲了简单明了的原则，这通常是一个坏主意，因为我们几乎无法预先知道哪些地方会影响性能。

在清晰度方面，您可以考虑使用Stream API代替常见的迭代方式：

Arrays.stream(arrayA)
    .flatMap(n1 -> Arrays.stream(arrayB).map(n2 -> n1 + n2))
    .filter(n -> n <= total)
    .count();

- sprinter

---

@pivovarit 真的吗？为什么？我在 OP 的问题中看不到任何关于计算不同对数的内容。 - sprinter

Answer 3

我们可以使用 O(m log m + n log m) = O(log m (m + n)) 的时间解决这个问题，其中 m 是较小数组的基数；n 是较大数组的基数。首先，对较小的数组进行排序：

A = {32,45,9,4};
B = {43,457,54,90};

=> A = {4,9,32,45}

现在对于B中的每个b，在A上使用二分查找来找到小于或等于(c-b)的最大a的索引。将(index+1)添加到累积结果中。例如：

c = 100:
  43  => 100 - 43  = 57   => largest a <= c-b = 45, index 3 => add 4 to result
  457 => 100 - 457 = -357 => largest a <= c-b = None
  54  => 100 - 54  = 46   => largest a <= c-b = 45, index 3 => add 4 to result
  90  => 100 - 90  = 10   => largest a <= c-b = 9,  index 1 => add 2 to result

result = 4 + 4 + 2 = 10
 corresponding with the following pairs:
 (43,4),(43,9),(43,32),(43,45),(54,4),(54,9),(54,32),(54,45),(90,4),(9,9)

- גלעד ברקן

---

这是一个非常直观的方法。它也不计算非不同对，这非常好。谢谢。 - Elroy Jetson

这是一个非常高效的解决方案。我会点赞两次。 - jetstream96

Answer 4

从对数组进行排序开始是个好主意。我会从最大值开始向下处理，找到哪些索引的值小于 c:

public static int pairs(int a[], int b[], int c) {
    // a and b should be sorted before being passed here

    // Find the largest a that has a pair under c:
    int amax;
    int bmax_for_a;
    for (amax = a.length; amax > 0; amax--) {
        for (int bmax_for_a = b.length; bmax_for_a > 0; bmax_for_a--) {
            if (a[amax] + b[bmax_for_a] <= c) {
                break;
            }
        }
    }

    // Find the largest b that has a pair under c:
    int bmax;
    int amax_for_b;
    for (bmax = b.length; bmax > 0; bmax--) {
        for (int amax_for_b = a.length; amax_for_b > 0; amax_for_b--) {
            if (a[amax_for_b] + b[bmax] <= c) {
                break;
            }
        }
    }

    // Now that we have the indexes, calculate the total matches
    // and discard duplicates:
    return (amax * bmax_for_a) + (bmax * amax_for_b) - (amax_for_b * bmax_for_a);
}

- Mureinik

Answer 5

我喜欢将两个列表排序并寻找极端情况的想法。然而，只有当数组中的数字也具有模式时，这才能很好地工作。（例如，{1, 2, 3' ...}或{1, 3, 5, ...}），因为你可以为该特定模式设计特定算法。

一种减少不必要循环的方法是对两个数组进行排序，并获取最小数。并检查在哪个索引处您不再需要查找配对。例如：
- 假设A= {1, 5, 6, 12}和B {1, 2, 3, 4, 5, 6}，并且c为7。
- 对于数组A，最小数为1。这意味着在数组B中的索引5之后没有匹配项，这意味着您必须迭代到索引5。
- 对于数组B，最小数也是1。在索引2之后不应该存在任何可能的配对。

这样，您可以截断两个数组的一部分，但仍然需要检查该点之前的每个索引，因为没有保证所有可能的配对都满足预设条件。

- n247s

Answer 6

考虑利用NavigableSet进行排序和使用它的headSet方法，您觉得如何？

public int countPairs(int[] a, int[] b, int c) {
    NavigableSet<Integer> aSet = IntStream.of(a).boxed().collect(Collectors.toCollection(TreeSet::new));
    NavigableSet<Integer> bSet = IntStream.of(b).boxed().collect(Collectors.toCollection(TreeSet::new));

    int total = 0;

    for (int aVal : aSet) {
        int max = c - aVal;
        Set<Integer> bVals = bSet.headSet(max, true);
        total += bVals.size();

        // Optimization to break from loop once there are no values small enough to satisfy the condition
        if (bVals.isEmpty()) {
            break;
        }
    }

    return total;
}

这假设对于 a = [0, 1], b = [0, 1], c = 5，0, 1 和 1, 0 是不同的一对。它还将每个数组中的重复项聚集在一起，但可以通过添加一些记录来处理（这会使算法更难跟踪）。

- David Ehrmann