如何优化未排序数组两数之和代码的时间复杂度？

针对未排序数组的两数之和判断问题，原双重循环代码的时间复杂度是O(n²)，可以通过以下两种方式优化：

方法一：用哈希集合实现O(n)时间复杂度 #

遍历数组时，用集合记录已经访问过的元素。对当前元素，计算需要的补数（目标值减去当前元素），如果补数在集合里，说明存在符合条件的两个元素；否则把当前元素加入集合继续遍历。

代码实现：

function find(arr, target) {
    const seen = new Set();
    for (const num of arr) {
        const complement = target - num;
        if (seen.has(complement)) {
            return true;
        }
        seen.add(num);
    }
    return false;
}

这个方法用O(n)的空间换O(n)的时间，集合的查询和插入操作平均都是O(1)，整体效率比原代码高很多，适合大多数场景。

方法二：排序+双指针实现O(n log n)时间复杂度 #

先给数组排序，再用两个指针分别从数组首尾向中间移动：

• 两指针元素和等于目标值，直接返回true；
• 和小于目标值，左指针右移（找更大的数）；
• 和大于目标值，右指针左移（找更小的数）；
• 指针相遇还没找到，返回false。

如果不想修改原数组，可以先复制数组再排序：

function find(arr, target) {
    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 === target) {
            return true;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return false;
}

这个方法时间主要消耗在排序的O(n log n)，比O(n²)高效，空间复杂度更低（允许修改原数组的话可以做到O(1)），适合对空间占用有要求的场景。

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