动态更新bing图片

力扣索引

001 两数之和 Easy

原始问题

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to _target_.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。
Input：nums = [2,7,11,15], target = 9
Output：[0,1]
Explanation：Because nums[0] + nums[1] == 9, we return [0, 1]

Input: nums = [3,2,4], target = 6
Output: [1,2]

Constraints:

  • 2 <= nums.length <= 103
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

    两层循环

    这道题是一个很简单的题，为什么这么说呢？因为作为第一题它条件很多，给你限制的死死的，只给你留了一条路走，毕竟，总不能上来就劝退吧。
    基本方法呢也是很简单两层循环解决问题，
    1. class Solution:
    2.   def twoSum(self, nums: List[int], target: int) -> List[int]:
    3.       i=0
    4.       while i<len(nums):
    5.           for j in range(i+1,len(nums)):
    6.               if nums[i]+nums[j]==target:
    7.                   return [i,j]
    8.           i+=1
    时间复杂度：O(n2/2),等差数列求和嘛，空间复杂度O(1)
    没有过多的讲解，那自然上面是常规做法，还有一些小优化

    通过字典模拟哈希求解

    一种以空间换时间的策略，建造hashmap肯定比建造链表消耗大，本题需要返回的是索引，使用set构建map会比较繁琐，这就用到了python内置的数据类型：枚举。
    1. class Solution:
    2.   def twoSum(self, nums: List[int], target: int) -> List[int]:
    3.       hashmap={}
    4.       for ind,num in enumerate(nums):
    5.           hashmap[num] = ind
    6.       for i,num in enumerate(nums):
    7.           j = hashmap.get(target - num)
    8.           if j is not None and i!=j:
    9.               return [i,j]
    利用内置的数据对象，减缓了遍历的时间，进而有所提高。
    时间复杂度：O(n)，空间复杂度O(n)。

    敢为天下先

    人外有人，天外有天。你所认为的天花板只是别人的垫脚石啊。所以普遍不是绝对，要自己多思考。
    1. class Solution:
    2.   def twoSum(self, nums, target):
    3.       number_bonds = {}
    4.       for index, value in enumerate(nums):
    5.           if value in number_bonds:
    6.               return [number_bonds[value], index]
    7.           number_bonds[target - value] = index
    8.       return None
    该解法在力扣时间复杂度排行榜上勇夺第一，也与大众解题想法想异。独特的解题方法使得数独又加快了。
    时间复杂度：O(n)，空间复杂度O(n)。