两数之和

001_two_sum

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

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

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

1.暴力破解

新手最容易想到的,暴力破解. 不占空间,但时间复杂度高O(n^2).

class Solution:
  def twoSum(self, nums, target):
    for i in range (len(nums)):
      for j in range (i+1,len(nums)):
        if nums[i]+nums[j]==target:
          return[i,j]
    return "null"
7748ms 7.2MB 5.46% 99.16%

2.暴力破解优化版&

其实这才是我直觉的算法,用目标数倒着判断 in list,比暴力版稍微好点,

class Solution:
  def twoSum(self, nums, target):
    for i in range (len(nums)):
      if target-nums[i] in nums:
        index = nums.index(target-nums[i])
        if index!=i:
          return [i,index]
    return "null"
1136ms 7.2M 52.88% 95.46%

3.字典备忘录~

优化的话,很容易就想到HashMap,Google一番发现python中的dict就是用的哈希表,这里用字典的话有点备忘录的意思

但发现个问题:看不懂dict和hashmap(java)的区别,先留个TODO在这里.

class Solution(object):
  def twoSum(self, nums, target):
    dic = {}
    for i, num in enumerate(nums):
      if num in dic:
        return [dic[num], i]
      else:
        dic[target - num] = i

68ms 8.1MB 59.03%


本文总字数: 886