优化嵌套循环：将O(n³)复杂度代码改进为O(n²)求助

我编写了一段JavaScript代码，用于计算数组中每一对元素的差值，并统计该差值在数组中的出现次数。当前代码的时间复杂度为O(n³)，希望将其优化至O(n²)。

原代码 #

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n;
let a = [];

rl.on('line', (line) => {
    if (!n) {
        n = parseInt(line);
    } else {
        a = line.split(' ').map(x => parseInt(x));
        let count = 0;
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                for (let k = 0; k < n; k++) {
                    if (Math.abs(a[i] - a[j]) === a[k] && i < j) {
                        count++;
                    }
                }
            }
        }
        console.log(count);
        rl.close();
    }
});

输入示例 #

5
3 1 4 2 1

预期输出 #

13

原代码问题分析 #

原代码的核心瓶颈在于：每计算出一对(i,j)的差值后，需要遍历整个数组（k循环）统计该差值的出现次数，这一步时间复杂度为O(n)。加上外层两层O(n²)的循环，整体时间复杂度达到O(n³)。

优化方案 #

预先统计数组中每个数字的出现次数，用哈希表（Map或普通对象）存储。每次算出差值后，直接从哈希表读取该差值的出现次数（O(1)操作），将整体时间复杂度降至O(n²)。

优化后的代码 #

完整输入处理版本

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n;
let a = [];

rl.on('line', (line) => {
    if (!n) {
        n = parseInt(line);
    } else {
        a = line.split(' ').map(x => parseInt(x));
        // 统计每个数字的出现次数
        const freqMap = new Map();
        for (const num of a) {
            freqMap.set(num, (freqMap.get(num) || 0) + 1);
        }
        
        let count = 0;
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                const diff = Math.abs(a[i] - a[j]);
                // 直接从哈希表获取次数，不存在则加0
                count += freqMap.get(diff) || 0;
            }
        }
        console.log(count);
        rl.close();
    }
});

测试代码片段

const n = 5;
const a = [3, 1, 4, 2, 1];

// 统计频率
const freqMap = new Map();
for (const num of a) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1);
}

let count = 0;
for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
        const diff = Math.abs(a[i] - a[j]);
        count += freqMap.get(diff) || 0;
    }
}
console.log(count); // 输出13，符合预期

优化说明 #

1. 预处理频率表：遍历一次数组，用O(n)时间统计每个数字的出现次数，存储在freqMap中。
2. 差值统计：遍历所有(i,j)对（O(n²)时间），计算差值后直接从freqMap中取出次数累加，避免了内层k循环，将这一步从O(n)降为O(1)。
3. 整体时间复杂度：O(n)（预处理） + O(n²)（差值统计）= O(n²)，达到优化目标。

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