两数之和II-输入有序数组 (opens new window)

• 难度：Easy
• 标签：Map 双指针

刷题思路

• [x] Map 暂存
• [x] 双指针夹逼

方法 1 Map 暂存

• 复杂度：
  • 时间 O(n)
  • 空间 O(n). 借助额外空间 Map
• 结果：
  • 执行用时：88 ms, 在所有 JavaScript 提交中击败了65.31%的用户
  • 内存消耗：38.2 MB, 在所有 JavaScript 提交中击败了8.75%的用户

var twoSum = function(numbers, target) {
    let map = new Map()
    for (let i=0, len=numbers.length; i<len; i++) {
        if (map.has(numbers[i])) {
            return [map.get(numbers[i])+1, i+1]
        } else {
            map.set(target-numbers[i], i)
        }
    }
};

方法 2 双指针夹逼

• 复杂度：
  • 时间 O(n)
  • 空间 O(1)
• 结果：
  • 执行用时：84 ms, 在所有 JavaScript 提交中击败了78.33%的用户
  • 内存消耗：37.8 MB, 在所有 JavaScript 提交中击败了18.04%的用户

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

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~