两数之和

力扣链接:https://leetcode.cn/problems/two-sum

关键信息

和为目标值两个整数

思路

一、 暴力循环

查找nums[i]+nums[j]=target

  • 时间复杂度:$$O(N^2)$$
  • 空间复杂度:$$O(1)$$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
var twoSum = function (nums, target) {
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    for (let j = i; j < len; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
};

二、哈希表

target - nums[i] = diff,循环判断map[nums[i]] !== undefined,如果成立则输出结果,否则将 diff 作为键,将 i 作为值存入哈希表。

  • 时间复杂度:$$O(N)$$
  • 空间复杂度:$$O(N)$$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
var twoSum = function (nums, target) {
  const map = {};
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    const diff = target - nums[i];
    const prevIdx = nums[i];
    if (map[prevIdx] !== undefined) {
      return [map[prevIdx], i];
    }
    map[diff] = i;
  }
};

注意事项

  • map[prevIdx] === 0map[prevIdx !== undefined含义不同,注意在分支语句中的隐式类型转换
  • 存入时的 keydiff,但查找时 key 则是用nums[i]

题目变种

待更新…