JavaScript中sumOfTwoItemExist函数的最优实现方案咨询

你用双重循环实现的方案逻辑是对的，但它的时间复杂度是O(n²)，当数组元素数量较多时，执行效率会明显下降。下面提供两种更优的实现思路：

1. 哈希表法（时间最优） #

思路 #

遍历数组时，用哈希表（JavaScript里用Set）记录已经遍历过的元素。对于当前元素num，计算需要的补数target = total - num，如果补数已经在哈希表中，说明之前遍历过的某个元素和当前元素之和等于total，直接返回true；否则将当前元素存入哈希表，继续遍历。

这种方法的时间复杂度是O(n)，空间复杂度是O(n)，用空间换时间，适合处理大数据量的数组。

代码实现 #

function sumOfTwoItemExist(arr: number[], total: number): boolean {
    const seen = new Set<number>();
    for (const num of arr) {
        const target = total - num;
        if (seen.has(target)) {
            return true;
        }
        seen.add(num);
    }
    return false;
}

2. 双指针法（空间最优） #

思路 #

先将数组排序，然后用两个指针分别指向数组的首尾：

• 计算两指针指向元素的和，如果等于total，返回true
• 如果和小于total，左指针右移（需要更大的数）
• 如果和大于total，右指针左移（需要更小的数）
• 直到两指针相遇，还没找到就返回false

这种方法的时间复杂度是O(n log n)（主要来自排序操作），空间复杂度是O(1)（如果使用原地排序的话），适合内存受限的场景。注意：如果不想修改原数组，需要先拷贝一份再排序。

代码实现 #

function sumOfTwoItemExist(arr: number[], total: number): boolean {
    // 拷贝原数组避免修改原数据，若允许修改原数组可直接排序
    const sortedArr = [...arr].sort((a, b) => a - b);
    let left = 0;
    let right = sortedArr.length - 1;
    while (left < right) {
        const sum = sortedArr[left] + sortedArr[right];
        if (sum === total) {
            return true;
        } else if (sum < total) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

方案选择 #

• 如果数组规模大、追求最快执行速度，优先选哈希表法
• 如果内存紧张、数组规模不大，优先选双指针法

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