java - 返回 (a, b) 对的总数，其中 a 来自 A，b 来自 B，且 a + b <= c

Question

尝试做一些练习，我遇到了这个问题......

Given two int arrays A and B, and an int c, return the total number of pairs (a, b) where a is from A and b is from B, and a + b is <= c

立即想出了蛮力解决方案，但似乎无法连接各个点以便以更好的时间复杂度来完成此操作。我尝试先对数组进行排序，然后尝试找到某种类型的模式，但这并没有让我到任何地方。我想到了一个数组有负数的情况。在这种情况下，我不能只查看 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;
    }
}

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