第一天我就來分享在 吳邦一教授的 python 581 系列文章的第一篇 Python-LeetCode 581 第一招 搜尋：有序、無序與爬行裡看到的技巧加上我個人刷題踩到的邏輯錯誤。

文章重點:

以 1 Two Sum 當作當作例子，討論搜尋技巧分為三類:

1. 線性搜尋: 當沒有更高效的方法時才使用
2. 排序過後二分搜
3. 字典搜尋: 使用 Hash Table 做常數時間的搜尋

Two Sum 題目概要：

在這道題中，我們需要在一個數列中找到兩個數，這兩個數的和等於給定的目標值（target），並且它們在數組中的位置不能相同。解題的關鍵在於利用字典進行搜尋，並且避免某個元素與自己相匹配，也就是主題講的 "別踩到自己"，搜尋範圍的資料不會因為迭代過程增刪錯誤資訊進去。

常見避免踩到自己的方法不只一種，如:

1. 將舊新資料分開
2. 「有順序的控制自己不要踩到自己拉的屎」，前面的動作不可以影響到後續的動作，最終導致錯誤。

如何在 Two Sum 這題「避免踩到自己」?
建一個字典，每個元素先字典裡搜尋是否有相匹配在前面的元素中搜尋，然後在把自己加入字典，這樣就不會搜到自己了! 而不是這題先把所有的元素存進字典，才做搜尋。

以下是我 「踩到自己」的例子:

我在 80. Remove Duplicates from Sorted Array II犯的錯誤。

題目敘述

給一個 non-decreasing 排序的整數數組 nums，相同元素最多出現兩次，超過要 in-place 的刪除。元素的相對順序應保持，k 是刪除過後，陣列中重複不超過 2 的元素總個數。測試時只考慮數組前 k 個元素，前 k 以外都無所謂。題目最終返回 k。

我的想法:
這題與 Remove Duplicates from Sorted Array 類似，會用 Two Pointer 的方式，分別記錄迭代陣列的索引與紀錄目前確定不重複元素的最後元素的索引。在這題裡允許每個元素可最多出現兩次，因此倘若向前兩個索引的值仍是相同那就不理會，其餘就寫入 j 位置，接著 j + 1。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() <= 2)
            return nums.size();
        int j = 2;
        for (int i = 2; i < nums.size(); i++) {
            if (nums[i] == nums[i-2])
                continue;
            nums[j++] = nums[i];
        }
        return j;
    }
};

我寫錯的地方在於 if (nums[i] == nums[i-2])， 因為 j <= i，因此我用 nums[i] 與 num[i-2] 判斷是否為重複元素就會有問題。 i 的值在迭代過程中會移動或被覆蓋，所 nums[i-2] 並不總是當前考慮的前兩個元素的值，因此，我應該是用 nums[i] 與 nums[j-2] 做是否寫入的判斷依據，因為 j 是紀錄已經處理好的部分，這樣才可以保證是處理好的資料。

我方法的時間複雜度是 O(n)，因為只需遍歷一次陣列。