1 二分法

704 二分查找

題目：
給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標值 target ，寫一個函數(shù)搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。

示例

輸入: nums = [-1,0,3,5,9,12], target = 9     
輸出: 4       
解釋: 9 出現(xiàn)在 nums 中并且下標為 4     

輸入: nums = [-1,0,3,5,9,12], target = 2     
輸出: -1        
解釋: 2 不存在 nums 中因此返回 -1     

前提：1. 有序數(shù)組 2. 無重復元素

要點

1. 循環(huán)不變量
   a. while(left < right) or while(left <= right)
   b. right = middle or right = middle - 1
   其實這兩者對應的是 [left, right) 左閉右開區(qū)間或者 [left, right] 左閉右閉區(qū)間。個人習慣是寫左閉右開，即 left < right 和 right = middle。左閉右開，對應初始化 left = 0; right = nums.size()，right 是取不到的，所以 left 不會等于 right，且 right 應更新為 middle。
   此外注意當 target > middle 的時候，left 應更新為 middle + 1，這是因為 middle 已經(jīng)不應在搜索范圍。
2. 中點的取法
   使用 left + (right - left) >> 1 是為了避免計算 left + right 的時候 overflow，>> 1 右移一位的運算相當于除以2。
3. 易錯注意 位運算的優(yōu)先級，需要加括號。

代碼

時間復雜度 O(N) 空間復雜度 O(1)

左閉右開

C++

class Solution {
      int search(vector<int>& nums, int target) {
          int left = 0;
          int right = nums.size(); // [left, right)
          while(left < right) {
              int middle = left + ((right - left) >> 1);
              if (target < nums[middle]) { // search left half
                  right = middle;
            } else if (target > nums[middle]) { // search right half
                  left = middle + 1;
            } else { // target == nums[middle]
                  return middle;
            }
        }
      return -1;
    }
};

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)
        while left < right:
            middle = left + ((right - left) >> 1)
            if target < nums[middle]:
                right = middle
            elif target > nums[middle]:
                left = middle + 1
            else:
                return middle
        return -1

左閉右閉

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int middle = left + ((right - left) >> 1);
            if (target < nums[middle]) {
                right = middle - 1;
            } else if (target > nums[middle]) {
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
};

2 雙指針

27 移除元素

題目：
給你一個數(shù)組 nums 和一個值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并原地修改輸入數(shù)組。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。
示例 1: 給定 nums = [3,2,2,3], val = 3, 函數(shù)應該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。 你不需要考慮數(shù)組中超出新長度后面的元素。
示例 2: 給定 nums = [0,1,2,2,3,0,4,2], val = 2, 函數(shù)應該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4。
*你不需要考慮數(shù)組中超出新長度后面的元素。

要點

1. 暴力解法 千萬注意size--的同時 i--，這是因為去掉一個值后的數(shù)組 index 也會左移一位。
2. 雙指針即使用一層循環(huán)做雙層循環(huán)的事。注意確定什么時候動左指針，什么時候動右指針的條件。
3. 同向雙指針。對快指針遍歷，當遇到與 val 不同的值的時候慢指針才會移動，否則快指針遇到等于 val 的值，不應被保留，快指針不動，nums[i] 不更新。

代碼

暴力雙循環(huán)法

先在外層遍歷i，當 nums[i] = val 的時候，j 從 i+1 開始遍歷到小于 nums.size()，并賦值 nums[j-1] = nums[j]（這里要注意循環(huán)不變量的問題）。
時間復雜度 O(N^2) 空間復雜度 O(1)
C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // O(N^2)
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < size; j++) {
                    nums[j-1] = nums[j];
                }
                i--;
                size--;
            }
        }
        return size;
    }
};

雙指針法

1. 快慢指針、同向雙指針
   時間復雜度 O(N) 空間復雜度 O(1)
   C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // O(N)
        int size = nums.size();
        int i = 0;
        for (int j = 0; j < size; j++) {
            if (val != nums[j]) { // when j not equal to val
                nums[i++] = nums[j];
            }
        }
        return i;
    }
};

2. 相向雙指針
   時間復雜度 O(N) 空間復雜度 O(1)
   有些難以理解。先保留在這。