通过字典方式实现

  • 时间复杂度：O (n)

  • 空间复杂度：O (n)

    1. function twoSum(nums, target) {
    2.   const map = new Map();
    4.   for (let i = 0; i < nums.length; i++) {
    5.       const item = nums[i];
    7.       const need = target - item;
    9.       if (map.has(need)) {
    10.           return [map.get(need), i];
    11.       } else {
    12.           map.set(item, i);
    13.       }
    14.   }
    15. }

代码中存在一个 for 循环，所以时间复杂度是 O (n) ，这里可能就会有同学问 map.has 也是遍历元素不算循环码？其实 map 不是数组，在内存中是不连续的，所以不是遍历，而是直接根据内存地址来查找的。开辟的空间只有 map 是受 nums 长度影响的，所以空间复杂度为 O (n)