数组a[i]*a[j]=a[k]（i≤j）三元组计数算法能否快于O(n²)？

问题背景 #

你需要统计数组中满足i ≤ j且a[i] * a[j] = a[k]的三元组(i,j,k)的总出现次数，目前已经实现了O(n³)的暴力解法和存在缺陷的O(n²)哈希解法。
首先修正你现有O(n²)实现的问题：你用HashSet仅判断乘积是否存在，没有统计符合要求的k的出现次数，当数组存在重复元素时结果会偏小。比如数组为[2,2,4,4]，正确计数为6，你的HashSet版本仅会返回3。正确的O(n²)实现应该用HashMap统计每个数值的出现频率，总次数需要乘以对应乘积值的出现次数，修正后代码如下：

public static int count(int[] a) {
    int total = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : a) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }
    for (int i : a) {
        for (int j : a) {
            if (i <= j) {
                total += freq.getOrDefault(i * j, 0);
            }
        }
    }
    return total;
}

低于O(n²)时间复杂度的可行性说明 #

特定场景下可以得到更优解

• 数组存在大量重复元素的场景
  可以先提取去重后的元素列表，设去重后元素个数为m，只需要遍历去重列表中所有满足x ≤ y的二元组计算贡献即可，时间复杂度为O(n + m²)，如果m远小于n，实际运行效率会远低于原生O(n²)。实现逻辑如下：
  1. 遍历原数组统计每个数值的出现频率freq，同时生成去重元素列表uniqueNums
  2. 遍历所有x ∈ uniqueNums、y ∈ uniqueNums且x ≤ y的组合：
     • 若x*y不在freq中则跳过
     • 若x != y，该组贡献为 freq.get(x) * freq.get(y) * freq.get(x*y)
     • 若x == y，该组贡献为 freq.get(x) * (freq.get(x) + 1) / 2 * freq.get(x*y)
• 数组元素为正整数且值域上限较小的场景
  可以用数组代替HashMap做频率计数，同时可以提前剪枝：如果x*y已经超过值域上限，直接跳过不需要查询频率，进一步降低常数开销。

通用场景不存在低于O(n²)的解法

对于任意元素、任意分布的通用场景，目前没有比O(n²)更低的时间复杂度解法。最坏情况下所有i ≤ j的二元组乘积都存在于数组中，必须枚举所有i ≤ j的组合才能得到正确计数，这一步的时间下界就是O(n²)。

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