01.leetcode题目讲解(Python):两数之和

题目:

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

这道题目比较容易想到的是通过暴力搜索求解,但暴力搜索的时间复杂度为 O(n^2)。如果使用哈希的思想,利用Python中list的查询方式,我们可以将复杂度降低到 O(n)。有两个值得注意的地方:

  1. 同样的元素不能重复使用(也就是不能自己加自己)
  2. 给定的数组中可能有相同的元素(比如 [3, 3, 4, 4, 5])

参考代码如下:

ps:如果您有好的建议,欢迎交流 😀