统计从四个数组各取一个元素且和≤k的组合数的最优算法

• 现有实现虽通过数组排序、循环中途提前break减少了无效判断，但本质仍是四层嵌套遍历全部四元组合，时间复杂度为与四个数组规模乘积正相关的O(n⁴)。当单个数组长度达到1000量级时，总运算量会突破万亿次，必然触发超时阈值，无法适配测试用例的规模要求。
• 提前终止的优化只能削减部分无效循环，无法从根本上降低复杂度量级，对长数组场景的性能提升极为有限。

核心思路是四元求和拆分为二元求和匹配，把复杂度从O(n⁴)压降到O(n² log n)，步骤如下：

• 拆分数组：将4个数组两两分为一组，分别计算两组内所有两两元素的和，生成两个新的和列表：
  • 取数组a、b，计算所有a_i + b_j的值，存入sumAB列表
  • 取数组c、d，计算所有c_m + d_l的值，存入sumCD列表
• 对sumCD列表做升序排序。
• 逐个遍历sumAB中的每一个和值s，计算需要匹配的目标值target = k - s：只要sumCD中存在值t满足s + t <=k，就说明这一组(s,t)对应一个合法的四元组合。
  • 因为sumCD已经有序，直接通过二分查找定位到sumCD中第一个大于target的元素位置，该位置的下标值，就是sumCD中所有满足t <= target的元素总个数
• 把所有sumAB元素匹配到的合法数量累加，就是最终的可行方式总数。

这个方案的整体时间复杂度为：生成两个和列表各需O(n²)，排序sumCD需O(n² log n)，遍历sumAB并逐次二分查找共需O(n² log n)，哪怕单个数组长度到2000级别，总运算量也仅在千万量级，完全不会出现超时问题。

public static long process(List<Integer> a, List<Integer> b, List<Integer> c, List<Integer> d, int k) {
    List<Long> sumAB = new ArrayList<>();
    for (int numA : a) {
        for (int numB : b) {
            sumAB.add((long) numA + numB);
        }
    }

    List<Long> sumCD = new ArrayList<>();
    for (int numC : c) {
        for (int numD : d) {
            sumCD.add((long) numC + numD);
        }
    }

    Collections.sort(sumCD);
    long total = 0;

    for (long s : sumAB) {
        long target = k - s;
        // 二分查找sumCD中第一个大于target的位置
        int left = 0, right = sumCD.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (sumCD.get(mid) > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        total += left;
    }

    return total;
}

实现注意点 #

• 计算元素和时要强制转long类型，避免两个int相加超出int取值范围导致精度错误。
• 二分查找的退出逻辑要严格和题目的总和判断条件对齐，不要出现多算、少算的边界错误。

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