基礎篇（二）：數組

數組有兩點要注意：

• 數組下标都是從0開始的。

• 數組記憶體空間的位址是連續的。

  正是因為數組的在記憶體空間的位址是連續的，是以我們在删除或者增添元素的時候，就難免要移動其他元素的位址（不能直接插入或删除）。

由于數組中的元素在記憶體中的位址是連續的，是以隻需要使用O（1）的時間就可以随機通路數組中的任意元素。

數組經典題目常用到的方法有： 二分法、雙指針法、滑動視窗、模拟行為

1.二分法

二分法的前提條件：被查資料必須有序(升序或降序)

二分法的三種情況（所有模闆）

• 第一種：最基本情況

int binary_search(int[] nums,int target) {
    int left=0,right=nums.length-1; 
    while(left<=right) {
        int mid=left+(right-left)/2;
        if(nums[mid] < target) {
            left=mid+1;
        }else if(nums[mid]>target){
            right=mid-1; 
        }else if(nums[mid]==target) {
            return mid;//直接傳回
        }
    }
    return -1;// 直接傳回
}
           

• 第二種：取左邊界（最左邊的）

int left_bound(int[] nums,int target){
    int left=0,right=nums.length-1;
    while(left<=right) {
        int mid=left+(right-left)/2;
        if(nums[mid]<target){
            left=mid+1;
        }else if(nums[mid]>target) {
            right=mid-1;
        }else if(nums[mid]==target) {
            right=mid-1;// 别傳回，鎖定左側邊界
        }
    }
    // 最後要檢查 left 越界的情況
    if(left>=nums.length||nums[left]!=target)
        return -1;
    return left;
}
           

• 第三種右邊界（最右邊的）

int right_bound(int[] nums, int target) {
    int left=0,right=nums.length-1;
    while(left<=right) {
        int mid=left+(right-left)/2;
        if(nums[mid]<target){
            left=mid+1;
        }else if(nums[mid]>target){
            right=mid-1;
        }else if(nums[mid]==target) {
            left=mid+1;// 别傳回，鎖定右側邊界
        }
    }
    // 最後要檢查 right 越界的情況
    if(right<0||nums[right]!=target)
        return -1;
    return right;
}
           

一般情況下會用第一種情況

704.二分查找 - 力扣

35.搜尋插入位置 - 力扣

2.雙指針

雙指針一般兩類，一類是「快慢指針」，一類是「左右指針」。前者主要解決連結清單中的問題，比如典型的判定連結清單中是否有環；後者主要解決數組（或字元串）中的問題，如二分查找。

141. 環形連結清單 - 力扣（LeetCode）

142. 環形連結清單 II - 力扣（LeetCode）

704. 二分查找 - 力扣（LeetCode）

3.滑動視窗

滑動視窗的應用場景

1.滑動：說明這個視窗是移動的，且視窗的移動是按照一定方向來的。

2.視窗：視窗大小并不是固定的，可以不斷擴容直到滿足一定的條件；也可以不斷縮小，直到找到滿足條件的最小視窗；當然可以是固定大小。

（用來解決一些查找滿足一定條件的連續區間的性質（長度等）的問題）

209.長度最小的子數組

3.無重複字元的最長字串

4.模拟行為

模拟顧名思義，就是按照題目給的操作，用代碼依次描述出來即可，就是這麼簡單。

模拟類的題目在數組中很常見，不涉及到什麼算法，就是單純的模拟，十分考察大家對代碼的掌控能力。

模拟過程：（1）讀題；（2）模組化；（3）代碼實作；（4）調試、優化