leetcode1-两数之和

jiezi

5 年前

欢迎跟着夏老师一起学习算法，这方面我自己的基础很薄弱，所以解题方法和思路也会讲的很”小白“，不需要什么基础就能看懂。

关注公众号可以进行交流和加入微信群，群内定期有系列文章分享噢！

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

 给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

通过第 1 遍循环可以拿到当前值和剩余值，然后嵌套循环一次，检查剩余值是不是在数组中。

function twoSum(nums, target) {for(let i = 0;i<nums.length;i++) {const current = nums[i]; // 拿到当前值
    const remain = target - current; // 拿到剩余值
    
    for(let j = 1;j<nums.length;j++) {if(nums[j] === remain) {return [i, j];
      }
    }
  }
}

时间复杂度是 O(n^2)

nums 的长度为 n, 嵌套循环的总执行次数是 n*(n-1)，当 n 趋向于无穷大时 n - 1 和 n 没什么区别，忽略

空间复杂度为 O(1)

增加的临时变量有 current, remain, i, j，不会随着 nums 的长度而增加，所以是常量 O(1)

嵌套循环的效率是最低的, 面试的时候就算回答出来被送走的几率也是很大的。

核心思想是使用一个 HashTable 保存每个值和每个值的位置。

第 1 次循环时构造出 HashTable，键为 nums 数组的元素，值为元素对应的下标

第 2 次循环时获取当前循环的值以及剩余值，如果剩余值的索引不等于当前值的索引，且剩余值也在 HashTable 中，直接从 HashTable 读取出当前值和剩余值的 index 返回。

function twoSum(nums, target) {const hashTable = {};
  // 第 1 次循环
  for(let i = 0;i<nums.length;i++) {hashTable[nums[i]] = i;
  }
  // 第 2 次循环
  for(let i = 0;i<nums.length;i++) {const current = nums[i];
    const remain = target - current;
    if(map[remain] !== undefined && map[remain] !== i) {return [i, map[remain]];
    }
  }
}

时间复杂度为 O(2n) = O(n)

进行了两次循环，理论上是 2 * n 的时间复杂度，但是当 n 趋向于无穷大时，n 和 2n 的差距可以忽略，所以结果是 O(n)

空间复杂度为 O(n)

增加了 HashTable，大小是 nums 的长度 n，所以空间复杂度是 O(n)

该算法利用了 HashTable 的 O(1) 的时间复杂度巧妙地减少了嵌套循环，算法效率提升很大！

一般回答到这里基本就没啥问题了，但是还有一种基于 HashTable 一次循环就能解决问题的方案。

循环 nums 数组，得到当前值和剩余值，判断剩余值在不在 HashTable，如果在的话，直接返回剩余值的位置和当前值的位置。如果不在则把剩余值插入 HashTable，继续循环。

Q: 为什么先返回的是剩余值的位置而不是当前值的位置？

A: 因为当前值的位置是确定的，所以当前值的位置不在 HashTable 中，但是剩余值可能在前面的循环中插入了 HashTable，是老值，所以先返回。

function twoSum(nums, target) {const hashTable = {};
  
  for(let i = 0;i<nums.length;i++) {const current = nums[i];
    const remain = target - remain;
    if(hashTable[remain] !== undefined) { // 为什么不需要判断位置? 因为当前值的位置根本没插入 HashTable 中，索引不可能重复
      return [hashTable[remain], i];
    }
    hashTable[current] = i; // 插入当前值到 HashTable，下一次循环时这里就成了 "老值"
  }
}

时间复杂度 O(n)

正宗的 O(n), 一次循环解决问题

空间复杂度 O(n)

增加了 HashTable，大小随着 nums 的增大而增大

两数之和是 leetcode 的第 1 个问题，也是比较简单的一个问题，对算法有畏难情绪的读者可以把心收到肚子里了，跟着夏老师一起学算法！
有疑问的读者可以扫描上方二维码和我沟通。

leetcode1-两数之和

问题

嵌套循环解题法

两遍 HashTable 解题法

一遍 HashTable 解题法

结尾