本文會提到做 array 常犯錯誤、如何避免，與常見的技巧。
此系列 Leetcode 篇不介紹基本資料結構。
[toc]

常見錯誤：複製到 list 的 reference

通常出現在 2d array，改動其中一個 list，其他 item 若有同 reference 也會一起變動。
新手很容易踩這種坑，然後 debug 底不出來。

時機

1. 複製 sublist
   nums[len(nums) - m:] = nums[:m]
   改成 nums[len(nums) - m:] = nums[:m].copy()
2. 2d list 初始化 (matrix)
   mylist = [[0] * 3 ] * 9
   改成 mylist = [[0] * 3 for _ in range(9)]
3. 2d dp 陣列

掌握基礎先備知識

為了避免踩這些不好除錯的雷，
請務必要弄懂 深淺複製、pass by copy of reference 等等 Python 基礎。

常見錯誤：index out of bound

寫程式第一個碰到的錯誤？
基礎但惱人。

平時多動腦：邊界練習

除了多寫以外，我沒事會做個邊界練習（？，不要養成用 run 來驗證邊界的壞習慣。
當發現某個題目寫到超界的時候，就可以拿來練習各種轉換一下，
這個回圈跑幾次、i 的範圍、換成 1 based 會怎麼跑？
例如：
given for i in range(9)
i = [0, 8]
這個回圈會跑 9 次
相等於
for i in range(0, 9)
如果 index 從 1 開始，
for i in range(1, 10)

還可以想想 <= 、 < 的轉換 或 while 與 for 的轉換
最好練到後期都不要噴邊界錯誤。

Two pointers

這不是什麼演算法，就只是用兩個指針指到的數值做處理。
我自己縮小這個定義範圍，只有輸入一個陣列，從頭尾同時取用陣列的問題，才算陣列的 two pointers。
重點是在看題目時，要意識到比起從頭到尾做，「兩邊一起做」或許比較好。
為什麼要兩邊一起做？可能陣列已經有排序過。
目標的數字要馬在 left pointer 的右邊，要馬在 right pointer 的左邊，兩邊同時看比較快
所以時間至少 O(NlogN)除非輸入早已排序。
167. Two Sum II - Input array is sorted
做過題目就會知道最快用 hashmap，但 two pointers 好處是不需額外空間

binary search 是個 two pointers 的應用。

除了排序好的，也有其他情形可能需要利用左右指針，並適當往內縮減的狀況：
11. Container With Most Water

Sliding window

減少重複做的事情。
最常碰到問題需要取 substring 做處理。
3. Longest Substring Without Repeating Characters

總結

今天不舒服先這樣，明天再來多修多補齊一些思路。

發現寫一寫已經有點忘記幾個月前的自己是怎麼想的了，
即使還記得曾經的 struggle，
開始有點變成某個思考是理所當然，
希望能在忘記之前都記下來。