相關代碼已經上傳到github：https://github.com/exploitht/leetcode-python

文中代碼為了不動官網提供的初始幾行代碼內容，有一些不規范的地方，比如函數名大小寫問題等等；更合理的代碼實現參考我的github repo

1、讀題

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

有一個整型數組，返回滿足特定條件的2個數字的索引，這2個數字相加的值等于特定的目標數字。假設每一次輸入都會有唯一的輸出而且同一個元素不會使用2次。

2、初步解題

很簡單的一個思路就是循環遍歷數組，做一個if判斷，滿足條件返回索引。編碼很簡單，如下：

class Solution(object):

def twoSum(self, nums, target):

"""

:type nums: List[int]

:type target: int

:rtype: List[int]

"""

# i從列表的第一個到倒數第二個，也就是nums[0, Len-2]

# j從i的后面一個開始到nums[Len-1]

# 下面的len(nums)-1而不是-2是因為range(1,2)返回的是[1]不含2

for i in range(0, len(nums) - 1):

for j in range(i + 1, len(nums)):

if nums[i] + nums[j] == target:

return [i, j]

3、第一次優化

上面的解決方案for套for明顯時間復雜度是O(n2)，這里的2是平方，空間復雜度是O(n)，思考一下有沒有優化的辦法的？

循環有嵌套，能不能不要循環套循環？

這里的循環嵌套是為了對每一個元素判斷一次序列中是否有匹配元素，有的話返回雙方索引，所以可以考慮在尋找匹配的元素這一步，不要一直去遍歷，如果元素值和索引生成一個哈希表，那么匹配的過程只要查詢哈希表就行了，這個過程的復雜度是O(1)，下面嘗試給出一種解決方案：

class Solution(object):

def twoSum(self, nums, target):

num_dict = dict()

# 第一次循環建立值和索引的哈希表

for index, value in enumerate(nums):

num_dict[value] = index

# 第二次循環判斷目標target-nums里的元素得到的結果是不是在前面得到的字典中，如果存在則返回雙方索引

for index, value in enumerate(nums):

if (target - value) in num_dict and num_dict[target - value] != index:

return [index, num_dict[target - value]]

4、第二次優化

上面一個方案通過2次循環(非嵌套)的方式，遍歷了2次nums列表得到了需要的結果，時間復雜度變成了O(n)。

美中不足的是循環還是進行了2次，這里是先生成一個哈希表，然后循環過程中判斷當前元素和哈希表中的數據相加是否滿足條件，第一次循環的過程中能不能做一個判斷呢？

所以下一個思路是遍歷nums，遍歷過程中判斷當前元素和哈希表中的值相加能不能滿足要求，也就是target-當前元素的值在哈希表中是否存在，如果存在，就返回2個索引，如果不存在，那么當前元素存入哈希表。實現如下：

class Solution(object):

def twoSum(self, nums, target):

num_dict = dict()

for index, value in enumerate(nums):

want = target - value

if want in num_dict:

return [num_dict[want], index]

num_dict[value] = index

聲明：文章中涉及的代碼全部本地手寫然后上傳到leetcode驗證通過，優化部分思路參考官網內容

總結

以上是生活随笔為你收集整理的leetcode two sum python_LeetCode专题-Python实现之第1题：Two Sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。