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]

2. 哈希表

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

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 []

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

四、總結

本文從題目描述、解題思路與實踐運用三個方面對Python編程題5級 小明進行了詳細的闡述，希望本文能對Python編程愛好者有所幫助。