LeetCode超时问题：如何优化JavaScript版Two Sum II代码？

你的双重循环解法时间复杂度是O(n²)，在数组规模较大时会超时，而题目给出的数组是非降序排列的特性，刚好可以用双指针法把时间复杂度降到O(n)，同时满足常数额外空间的要求，具体实现如下：

双指针思路 #

利用数组有序的特点，用两个指针分别从数组的首尾开始遍历：

• 计算两个指针指向元素的和：currentSum = numbers[left] + numbers[right]
• 若currentSum === target：直接返回[left+1, right+1]（因为题目要求1索引）
• 若currentSum < target：左指针右移一位（需要更大的数来凑目标和）
• 若currentSum > target：右指针左移一位（需要更小的数来凑目标和）

因为题目保证有唯一解，所以遍历过程中一定会找到符合条件的两个数，无需处理无结果的情况。

优化后的代码 #

var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    
    while (left < right) {
        const currentSum = numbers[left] + numbers[right];
        if (currentSum === target) {
            return [left + 1, right + 1];
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
};

为什么这个解法更高效 #

• 时间复杂度：O(n)，每个元素最多被访问一次，相比双重循环的O(n²)，在大数组下性能提升非常明显
• 空间复杂度：O(1)，只用到了两个指针变量，完全符合题目要求的常数额外空间限制

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