導航頁-LeetCode專題-Python實現

相關代碼已經上傳到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驗證通過，優化部分思路參考官網內容