Leetcode 1. Two Sum 两数之和 (python)

题目

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，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

例子

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

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

Example 3:

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

思路

第一个思路是双循环解题，即在每个元素上都遍历一次整个数组，求是否有符合条件的另一元素。但是这样算法复杂度将会是$O(n^2)$ 。 因为假设一个数组尺寸为n， 每遍历一次就是O(n), 要把整个数组的每个元素都检测一次也是O(n). 那么$O(n)\ast O(n)=O(n\ast n)=O(n^2)$

用其他方法优化，要怎么样减少不必要的检索呢？

用哈希表，把数值转为key, 下标作为value存进。

那么在遍历数组的时候，对元素进行目标值减去元素值的操作，再把得出的差值在key值里检索，如果找到，就把对应的value值返回get()。这样总的算法复杂度是$O(n)$.

优点在于，不用在每个元素都遍历一次数组，省去很多步骤。

代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = dict()
        # 把list存进dict里
        for i, element in enumerate(nums): # i是下标
            hashmap[element] = i
        # hashmap: {2: 0, 7: 1, 11: 2, 15: 3}
    
        for i, element in enumerate(nums):
            dif = target - element
            temp = hashmap.get(dif) #取出对应差值key的value下标
            # 当遇到target是某元素的双倍的情况，比如例子2和3：6-3=3
            # 如果有对应的key值（不为None）且所得下标和前面数组的标不相同的情况下才可以返还，避免查到同一个值
            if temp != None and i!= temp:
                return [i, temp]

              
        '''
        for i in nums:
            dif = target - i
            if dif in l and dif != i:
                return [l[i], l[dif]]
        # 当遇到target是某元素的双倍的情况的时候
        '''

最后

以上就是合适大地为你收集整理的力扣1. Two Sum 两数之和 (python)Leetcode 1. Two Sum 两数之和 (python)的全部内容，希望文章能够帮你解决力扣1. Two Sum 两数之和 (python)Leetcode 1. Two Sum 两数之和 (python)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。