Java原生数组场景下列表两两非等值组合和的数组长度预估问题

解决方案 #

你可以根据对空间和时间的接受度选以下两种方案： #

方案1：最大长度预申请+裁剪（优先推荐，实现最简单开销极低） #

你当前用的预估公式误差大的核心原因是没排除组合的重复计数：无序两两不重复下标的组合最大数量为n*(n-1)/2（n为原数组长度），这是所有元素都不相同时的和列表长度上限，不可能超过这个值。
操作逻辑：

1. 以上限为长度创建临时数组
2. 单次双层遍历填充符合条件的和，同时记录有效元素的下标
3. 最后调用JDK自带的Arrays.copyOf()方法裁剪临时数组得到最终结果
   这个方案没有额外的遍历开销，裁剪数组的时间复杂度为O(k)（k为有效元素数），远低于两次双层遍历的开销。
   示例代码：

import java.util.Arrays;

public class SumCalculator {
    public static void main(String[] args) {
        int[] origin = {1,2,3};
        int n = origin.length;
        // 预申请最大可能长度的数组
        int[] temp = new int[n * (n - 1) / 2];
        int validCount = 0;
        // 单次遍历计算和
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (origin[i] != origin[j]) {
                    temp[validCount++] = origin[i] + origin[j];
                }
            }
        }
        // 裁剪得到精确长度的结果数组
        int[] res = Arrays.copyOf(temp, validCount);
    }
}

方案2：频率预统计+精确长度申请（适合对空间浪费零容忍的场景） #

如果不能接受任何多余的空间申请，可以先花O(n)的时间统计元素出现频率，计算出精确的有效组合数，再创建对应长度的数组计算和，额外开销极低完全符合你的时间要求。
有效组合数计算公式：

精确长度 = 总两两组合数 - 所有重复元素的内部组合数
总两两组合数 = n*(n-1)/2
单个重复元素的内部组合数 = cnt*(cnt-1)/2（cnt为该元素的出现次数，仅cnt≥2时需要扣除）
示例代码：

import java.util.HashMap;
import java.util.Map;

public class SumCalculator {
    public static void main(String[] args) {
        int[] origin = {1,2,2,3};
        int n = origin.length;
        // O(n)时间统计元素频率
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : origin) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        // O(m)时间计算精确长度（m为不同元素的数量，远小于n）
        int exactLen = n * (n - 1) / 2;
        for (int cnt : freqMap.values()) {
            if (cnt >= 2) {
                exactLen -= cnt * (cnt - 1) / 2;
            }
        }
        // 创建精确长度的数组计算和
        int[] res = new int[exactLen];
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (origin[i] != origin[j]) {
                    res[index++] = origin[i] + origin[j];
                }
            }
        }
    }
}

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