這是一道LeetCode上的問題，詳見兩數(shù)之和，難度標(biāo)注是簡單，但是我思考到了一些比較復(fù)雜的情況，之后我會修改題目進(jìn)行討論的。

廢話不多，先看題：

給定一個整數(shù)數(shù)組和一個目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個數(shù)。你可以假設(shè)每個輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。

簡單的說，就是尋找到兩個數(shù)之和等于目標(biāo)值的兩個數(shù)序號，且只用尋找一個解。

暴力解法

尋找每一個搭配即可。

復(fù)雜度分析：

python代碼：

def twoSum(self, nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

哈希映射

上面的暴力求解法速度慢，主要的原因是優(yōu)于在確定第一個數(shù)之后，需要使用挨個遍歷的辦法來尋找另一個數(shù)是否存在，而在挨個遍歷的過程中，又帶來了時間復(fù)雜度O(n)，所以如果很快的尋找出另一個數(shù)的話，那么時間復(fù)雜度就可以降低了，理所應(yīng)當(dāng)?shù)南氲剑茏龅娇焖俨檎业霓k法就是散列表/哈希。

具體方法：

使用hash建立 item->index 的映射關(guān)系，通過 target-item 反向查找hash是否存在這個index，因為hash的查找時間是O(1)的時間復(fù)雜度，所以復(fù)雜度如下。

復(fù)雜度分析：

python代碼：

def twoSum(self, nums, target):
    # 產(chǎn)生散列表
    hash_ = dict(zip(nums, range(len(nums))))
    # 反向?qū)ふ?    for i in range(len(nums)):
        other=target-nums[i]
        if hash_.get(other):
            return [i,hash_[other]]

問題

從時間復(fù)雜度的方向考慮，哈希已經(jīng)可以做到很好了，但是實際情況中問題不是總是如題目中的簡單要求，因此可能會有下圖可能：
[圖片上傳失敗...(image-848eab-1532229850821)]

• 針對兩數(shù)之和等于目標(biāo)值 and 一個組合的情況上面的已經(jīng)給出解決方案
• 針對兩數(shù)之和等于目標(biāo)值 and 所有組合的情況可以在散列表產(chǎn)生的時候，不是采用鍵值覆蓋的方式，而是使用list表單存儲所有這個元素的位置，產(chǎn)生散列表的代碼如下（沒有經(jīng)過測試）

    # 原代碼：hash_ = dict(zip(nums, range(len(nums))))
    hash_={}
    for i in range(len(nums)):
        if hash_.get(nums[i]):
            # 如果存在hash，那么就存儲進(jìn)去
            hash_[nums[i]].append(i)
        else:
            hash_[nums[i]]=[i]

• 針對兩數(shù)之和接近目標(biāo)值 and 一個組合/所有組合的情況，就不能再使用散列表的方法了，因為散列表能夠工作的原因就是在知道第一個數(shù)的時候，另一個數(shù)會唯一確定，因此可以反向查找，但是現(xiàn)在不成立，我這里提供了另一個辦法（也是針對題目的要求，但是也可以修改后針對這種要求），時間復(fù)雜度略有損失。

有序線性查找

先進(jìn)行排序，然后根據(jù)有序性，線性查找。

具體步驟：

1. 升序排序，我使用的是merge排序，但是因為最后希望找到序號的值，所以不能直接排序，而是排列序號，在numpy中可以使用argsort排序
2. start指針指向第一個元素，嘗試尋找start指針和end指針之和剛剛大于等于target的end指針位置，也就是end指針的位置是大于等于target的，但是end指針之前的位置是小于target的
3. 開始尋找，如果之和小于target，那么start增加；如果之和大于target，那么end減少，知道start和end指針相遇。針對為什么小于target時start增加，而非end增加，因為end在這個步驟中的操作是減少，之前（也就是比end大）的值已經(jīng)搜索過了，反之亦然。

復(fù)雜度分析：

python代碼，不包含第三方庫（也可以使用numpy.argsort）

from math import floor
from copy import copy as py_copy

def argsort(nums):
    arg = list(range(len(nums)))

    def get(i, list_index=None):
        if list_index is None:
            list_index = arg
        return nums[list_index[i]]

    def set(i, index):
        arg[i] = index

    def copy(start, end):
        return py_copy(arg[start:end + 1])

    def sort_merge_core(start, end):
        """
        merge排序
        分治策略：
        分解：數(shù)組二分，每個小數(shù)組排序
        解決：對于最小的數(shù)組，長度1，不需要排序
        合并：兩個有序的數(shù)組，合并成為一個有序的數(shù)組
        start：排序的頭指針，包括本身
        mid：分解的中間指針，i~j是分解的第一個數(shù)組，j+1~k是分解的第二個數(shù)組
        end：排序的尾指針，包括本身
        """
        if start < end:
            mid = floor((start + end) / 2)
            sort_merge_core(start, mid)
            sort_merge_core(mid + 1, end)
            merge(start, mid, end)

    def merge(start, mid, end):
        """
        合并
        i1：第一個數(shù)組的指針，還沒有發(fā)到的位置
        i2：第二個
        index：發(fā)牌的指針，指向A，說明將要需要放置的位置
        """
        i1, i2 = 0, 0
        A1 = copy(start, mid)
        A2 = copy(mid + 1, end)

        for index in range(start, end + 1):
            if i2 == len(A2) or i1 != len(A1) and get(i1, A1) < get(i2, A2):
                set(index, A1[i1])
                i1 += 1
            else:
                set(index, A2[i2])
                i2 += 1

    sort_merge_core(0, len(nums) - 1)
    return arg


def twoSum(self, nums, target):
    start = 0
    end = len(nums) - 1

    # 從小到大排序，并保存原來的順序
    nums_index = argsort(nums)

    def getSum():
        return nums[nums_index[end]] + nums[nums_index[start]]

    # start和end之和剛剛大于等于target
    while getSum() > target:
        end -= 1
    if getSum() < target and end + 1 < len(nums):
        end += 1

    # 開始尋找，如果小于start增加，如果大于end減少
    while True:
        if start >= end:
            return None
        if getSum() < target:
            start += 1
        elif getSum() > target:
            end -= 1
        else:
            return sorted([nums_index[start], nums_index[end]])

結(jié)語

這個題目本身并不復(fù)雜，但是我認(rèn)為這種深入思考的方式，還是要堅持的使用，舉一反三，事半功倍。歡迎來我的github逛逛，還有我的博客。如果有什么問題或者探討，留言和email(jingege315@gmail.com)都是歡迎的。

參考/推薦

1. 兩數(shù)之和LeetCode官方解答（java版）
2. Markdown公式和列表教程
3. 我的實例代碼