Python编程题5级小明

本篇文章将从以下几个方面对Python编程题5级小明进行详细阐述。

一、题目描述

小明最近学习了Python，并通过了Python编程题5级，他接下来想要练手，给定一个整数列表和一个目标值，请在列表中找到和为目标值的两个整数，并返回它们的下标。假设每种输入只会对应一个答案，但是你可以不按照任何顺序返回答案。

def twoSum(nums: List[int], target: int) -> List[int]:
    pass

二、解题思路

1. 暴力枚举

最暴力的方法当然是枚举，这种方法的时间复杂度为O(n^2)，并不是一个好的解法。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

2. 哈希表

使用哈希表可以降低时间复杂度，将时间复杂度降低为O(n)，使用哈希表的思路就是维护一个映射关系，将每个数对应的下标存储下来。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i, num in enumerate(nums):
            if target - num in hashmap:
                return [hashmap[target - num], i]
            hashmap[num] = i
        return []

解释一下这段代码，我们用一个字典来存储每个数的下标，具体实现步骤如下：

1. 遍历数组nums，将每个数num与对应的下标i插入字典hashmap中。

2. 遍历数组nums，每次计算出还需要的target - num的值，如果在字典hashmap中出现过，就可以直接返回两个数的下标。

注意：这种方法只能用于本题，如果是求解多数之和，哈希表就不是那么好用了。

三、实践运用

我们来用两个例子来实践运用上述两种思路。

1. 暴力枚举

给定nums = [2, 7, 11, 15], target = 9，期望输出 [0, 1]。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

s = Solution()
print(s.twoSum([2, 7, 11, 15], 9)) # [0, 1]