# Python-LeetCode 581 第一招 搜尋：有序、無序與爬行

我們以LeetCode上的第一題來說明示範Python常用的搜尋技巧。
[(題目連結) 1. Two Sum (Easy)](https://leetcode.com/problems/two-sum/)
題目非常簡單：給一個整數陣列$nums$以及一個整數$target$，請找出兩個元素nums[i]與nums[j]，滿足$nums[i]+nums[j]=target$。

在這個題目中，它假設每一組測資都恰好有一組解，而且不可以找兩個相同的位置，也就是$i \neq j$。
這個題目雖然是Easy，但其實有不少可以拿來教學的東西。
最直接的方法是枚舉所有可能的$i$與$j$。

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

即使我們很聰明的讓$j$從$i+1$開始跑，只尋找$i<j$的部份，這個程式的時間複雜度仍然是$O(n^2)$，題目陣列長度的限制是$10^4$，所以直接枚舉不是個好的方法。

## 排序與二分搜

陣列中要搜尋某個數值最容易想到的就是二分搜，枚舉每一個元素$p$，我們的目標是找到$target-p$是否存在陣列中。
如果我們先將陣列依照數值由小排到大，使用二分搜可以在$O(\log n)$的時間找到某個元素是否存在，那麼時間複雜度將會是
$O(n\log n+n\log n)=O(n\log n)$，
因為排序是$O(n\log n)$，之後做$O(n)$次搜尋，每次$O(\log n)$。所以我們第一個可行的解法就是排序後二分搜。
如果只是要找兩個元素的數值會比較容易，這題是要找出兩個元素在原始陣列中的位置，我們依照數值排序會打亂掉原始的位置，因此我們要紀錄他們原始的位置。
請看以下的程式：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        a = sorted([(p,i) for i,p in enumerate(nums)])
        for p,i in a:
            j = bisect_left(a,(target-p,i+1))
            if j<len(a) and a[j][0]==target-p:
                return [i, a[j][1]]
        

這裡有些Python語法知識我們逐一解釋。
第3行我們建立一個陣列$a$，這個陣列每一個元素是一個tuple(中文翻譯為元組，聽起來好想吃麻糬)，包含兩個欄位，第一個是原陣列的數值，第二個欄位是它的位置(index)，這個陣列建立後會將他排序。sorted()跟.sort()很像，但sorted()會回傳而後者不會，所以不可以寫p=a.sort()，sort如果不熟需要查文件弄清楚。指令中的enumerate(nums)也是常用迴圈形式，可以產生對於所有i(從0到len(nums)-1)的(i,nums[i])物件。這裡的元組改成list也可以。
如果慢慢寫可以用以下迴圈的方式來建構：

a = []
for i in range(len(nums)):
    a.append((nums[i],i))
a.sort()

第4行是一個歷遍的迴圈，對$a$中的每一個元素$p,i$，這裡的寫法是自動unpacking，已知a中的元素是兩個欄位的元組，用 'p,i in a'會將元組的兩個欄位指定給p與i。

第5行是python的二分搜，在$a$陣列中找第一個 $>= (target-p,i+1)$的位置，LeetCode會幫我們import常用的函數，所以不必寫import。我們key值這樣給的原因是陣列中可能有相同元素，如果$target-p == p$的狀況，我們希望找到另外一個$p$。同時我們要知道Python在比較tuple或list時，是根據字典順序(lexicographic order)，也就是先比第一個欄位，如果前面的欄位都相等，就會比下一個欄位。
當找到時，我們在第7行回傳所要的答案。本題保證恰有一組答案，所以迴圈內必有成功之時，不必在迴圈後再回傳。

## 沿路二分搜不如一路爬行

前面的程式在排序後，我們枚舉$a$中的每一個元素$p$，用二分搜找到他可能的同伴$target-p$。想一想，排序後枚舉的元素數值是由小到大，那麼它的可能同伴必然是由大到小，也就是說bisect_left所得到的index $j$ 必然是由大到小移動，既然「一路向左，永不回頭」，那就不必搜，改成一路爬過去就可以了，因為一路向左爬過去沒有回頭過，很顯然 $j$ 總共走的距離只有$O(n)$，這樣比$n$次的$\log n$還要好。
以下是範例程式，同樣的因為保證有解，省略了一些檢查無解的動作。這個方法有時稱為雙指針爬行，有幾種不同(但類似)的寫法。這裡我們以 $i$ 為主角，用for迴圈歷遍 $i$，迴圈內用while迴圈將 $j$ 往前移動，要保持的迴圈不變性是
$a[i][0]+a[j][0]<=target$。
當其不滿足時，就持續將 $j$ 往左移動。這個while迴圈通常會加上$j>i$的範圍檢查來避免超界，因為題目保證有解，這個情況是不可能發生的，所以就省略了。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        a = sorted([(p,i) for i,p in enumerate(nums)])
        n = len(a)
        j = n-1
        for i in range(n):
            while a[j][0] > target-a[i][0]:
                j -= 1
            # if j<=i: no solution, but never happen 
            if a[j][0] == target-a[i][0]: 
                return [a[i][1], a[j][1]]
        

請注意，雖然外迴圈跑$O(n)$次，而 $j$ 在某次內迴圈中可能移動很大，甚至$O(n)$，但不可將時間複雜度估為$O(n\times n)=O(n^2)$，因為整個來說，內迴圈的執行次數只是$O(n)$，這種算總帳的分析方式，稱為amortized analysis(均攤分析)。

## 字典搜尋
搜尋除了有順序的二分搜之外，還可以運用字典搜尋。集合(set)與字典(dictionary)其實都是稱為hash table(雜湊表)的一種資料結構，背後有複雜的數學基礎，欲知詳情可以網路上查文件。對使用者來說，我們只要知道在通常的狀況下，他只需要$O(1)$的時間就可以查詢某個鍵值在不在、增加一個元素或刪除一個元素。所謂通常的情況其實是指雜湊表的密度不大時，也就是丟進去的東西不要太多。

集合只有鍵值，而字典則增加一個欄位，每一個鍵值可以對應到一個物件，該物件可以是個數字，一個list，甚至是一個集合或字典。Python的集合與字典使用起來非常方便，兩者的表示方法有點像，小心不要弄混。如果完全不了解，建議先看一下說明文件或基本操作的教學，網路上很容易查得到。這裡我們著重在如何運用它。

我們的計畫是建立一個字典，將陣列元素的值當做鍵值，而元素的位置當作是字典的對應值，對於一個元素nums[i]，我們去字典中搜尋$target-nums[i]$，如果找到，就找到答案。這裡有兩個細節問題要處理：
1. 字典的鍵值必須唯一不可重複。本題因為保證答案唯一，所以我們不必存多個相同的鍵值。
2. 我們要避免某個元素搜到自己，也就是類似$nums[i]=5$而$target=10$這種狀況。

「避免踩到自己」其實是程式設計中常常碰到的狀況，例如我們有一個list $s$，我們要將$s$中的偶數都刪除，暫時不管效率好壞，有人會這麼寫：

s = [1,2,3,4,5]
for i in range(5):
    if s[i]%2==0: s.pop(i)
print(s)

其中s.pop(i)是在列表中刪除第i個元素，但執行看看就發現完蛋了，跟表面上的不一樣。原因是在歷遍的過程中，我們修改了容器的內容，前面做的動作，影響了後面，自己踩到自己拉的屎。這其實是程式的大忌，即使控制得宜也是很不好的方式。
解決的方法不只一種，一種方式原則是將舊的與新的分開。在這個例子中，我們可以把活下來的寫到另外一個列表

s = [1,2,3,4,5]
t = []
for i in range(5):
    if s[i]%2: t.append(s[i])
s,t = t,s
print(s)

另外一種解決方式就是有順序的控制自己不要踩到自己拉的屎。我小時候有個鄰居養羊，每天帶羊出門吃草，跟狗不一樣，羊是一面走路一面拉屎，但羊為何都不會踩到自己拉的屎呢(踩到別羊的屎是另外一個故事)？原因很簡單，羊往前走，屎往後拉。上面的例子，如果我們由後往前做就可以正常運作了。理由很簡單，歷遍的過程中，先做的事情沒有影響後面。

s = [1,2,3,4,5]
for i in range(4,-1,-1):
    if s[i]%2==0: s.pop(i)
print(s)

回到我們的問題，我們要建一個字典，但要避免元素搜到自己，要怎麼辦呢？我們由前往後掃描，每個元素先在前面的元素中搜尋，然後在把自己加入字典。也就是我們只從後面的找前面的，每個元素搜完了才把自己加入，這樣就不會搜到自己了。
以下是Python範例程式。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {} # dict for previous value:index
        # we needy only one index since exactly one ans
        # never search to itself
        for i,p in enumerate(nums):
            if target-p in d: # search its partner
                return [i,d[target-p]]
            d[p] = i # insert itself 
             

在第3行我們建立一個空的字典。第6行的迴圈枚舉每一對$(i,p), nums[i]=p$，找看看$target-p$是否在$d$中，如果有，則找到答案了，同伴所在的位置就是$d[target-p]$，搜尋完畢後，再將自己加入字典。
請注意字典的對應值存取的語法與列表一樣都是用$[\; ]$。

## 結語

一般來說，搜尋有線性搜尋，二分搜，字典搜尋三種，各有不同的運用場合，線性搜尋的效率差，只有不得已而為之，二分搜是用在有序的場合，字典搜尋是用在無序的場合但必須是搜尋無誤差的值。
曾經在網路上看到某廣告說字典搜尋是二分搜尋的進階技能，哀呀，我的老天鵝，補習班的小編永遠都會是我們歡樂的來源。在這個問題上雖然兩個方法都可以，但更常見的狀況是我們要找兩個值，其和最接近但未必等於某個$target$，這個時候字典搜尋就沒戲唱了。
雙指標爬行還有一些不同的樣貌，在本題中是由外向內，也有時候是兩指標同一個方向，也有在兩個不同序列中移動的情形，以後應該還會有機會再碰到。
集合與字典的運用也非常多，python的key值不一定要是一個整數，很多時候它可以是個字串，甚至是個tuple，以後也會碰到。