17

【leetcode每日两题】-Day1-简单题

 3 years ago
source link: http://www.cnblogs.com/gokublog/p/13419104.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

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

所以返回 [0, 1]

class Solution:
    #哈希
    def twoSum(self, nums: List[int], target: int) -> List[int]: # nums = [2, 7, 11, 15] target = 9
        hashmap = {}
        for i in range(len(nums)): # i= 0,1,2,3
            if (target - nums[i]) in hashmap: # target = 9 target -nums[i] = 7 , 2 , -2 , -6
                return [nums.index(target - nums[i]),i]
            # 错误:hashmap.get(i) = nums[i] # {0:2,1:7,2:11,3:15}
            hashmap[nums[i]] = i

做题思路：

本题要求我们根据target返回nums中符合条件的索引并放在一个list中，考虑到这里，我们可以考虑哈希表，因为哈希表这种key-value形式可以减小数据查找的时间复杂度，将时间复杂度从两层循环的o(n2)降低为o(n)。代码中

hashmap[nums[i]] = i就是给哈希表中的kay-value赋值。需要注意的是python语言不想java等其他语言需要声明数据类型，所以在python做题当中经常用dict类比hashmap，用list类比queue和stack等等

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/two-sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK