什么時候用雙指標，該咋用？

雙指標思想

雙指標是我們做題中經常用到的思想，所以這個在刷題初期是一定要會的，其實我們早就學習過這個方法，我們通過二分查找來描述一下這個思想，

二分查找首先定義兩個指標，左指標和右指標，分別指向陣列的頭和尾，然后計算出他倆的中間的索引，其值和目標值進行比較，如果目標值更大則說明目標值在中間索引和右指標中間，則需要移動左指標到中間索引的后一位，如果目標值比中間值小，則需要移動右指標到中間索引的前一位，不斷執行，直至找到目標值，或當該陣列不含有目標值，左指標和右指標重合時跳出該回圈，

二分查找代碼

 public static int halfnum(int[] arraynum ,int b){
            int hi =arraynum.length-1;
            int lo = 0;
            //先判斷陣列是不是空
            if (arraynum.length==0){
                return -1;
            }            
            while(hi>=lo){
                 //判斷是否等于要猜的數
                if(b==arraynum[(hi+lo)/2]){
                    return (hi+lo)/2;
                }
                //大于中間數的情況
                else if (b>arraynum[(hi+lo)/2]){
                    lo= (hi+lo)/2+1;
                }
                //小于中間數的情況
                else{
                    hi=(hi+lo)/2-1;
                }
            }
           return -1;
        }

35.搜索插入位置

給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，你可以假設陣列中無重復元素，

示例 1:

輸入: [1,3,5,6], 5
輸出: 2

示例 2:

輸入: [1,3,5,6], 2
輸出: 1

示例 3:

輸入: [1,3,5,6], 7
輸出: 4

示例 4:

輸入: [1,3,5,6], 0
輸出: 0

題目很好理解，但是我們想要一次AC是不太容易的，我們根據題意可以想到，這樣共有四種可能

插入情況無非就這幾種

（1）比陣列里的任何值都小，插入頭部

（2）比陣列里的任何值都大，插入尾部

（3）查詢到陣列元素，回傳該處索引值

（4）陣列內無該元素，將其插入兩元素之間，

所以我們可以通過以下代碼實作該題

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            //中間值，與target對比
            int mid = (left + right) / 2;
            //第三種情況
            if(nums[mid] == target) {
                return mid;
            //移動左指標
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                //移動右指標
                right = mid - 1;
            }
        }
        //1，2，4三種情況都在回圈內部，我們只需輸出左指標即可，
        return left;
    }
}

剛才我們說了雙指標思想的重要性，下面這個題目也是可以完全通過雙指標思想實作的，所以說雙指標的思想是必須有的，你可以通過下面這個題目完全體會到雙指標的重要性

27.移除元素

給你一個陣列 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并回傳移除后陣列的新長度，

不要使用額外的陣列空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入陣列，

元素的順序可以改變，你不需要考慮陣列中超出新長度后面的元素，

示例 1:

給定 nums = [3,2,2,3], val = 3,

函式應該回傳新的長度 2, 并且 nums 中的前兩個元素均為 2，

你不需要考慮陣列中超出新長度后面的元素，

示例 2:

給定 nums = [0,1,2,2,3,0,4,2], val = 2,

函式應該回傳新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4，

注意這五個元素可為任意順序，

你不需要考慮陣列中超出新長度后面的元素，

該題目我們可以創建兩個指標，一前一后，前面的負責探路后面的負責填充，當前面查詢到需要移除的元素時直接跳過該元素，繼續前進，后面的指標只負責往該陣列里面填充不需要移除的數字，所以我們可以根據以下代碼實作

class Solution {
    public int removeElement(int[] nums, int val) {
    //特殊情況
      if(nums==null){
          return 0;
      }     
      int j = 0;//慢指標，i代表快指標
      for(int i = 0;i<nums.length;i++){
         //正常情況直接賦值給i          
          if(nums[i]!=val){
              nums[j]=nums[i];
              j++;
          }
          //如果為需要洗掉的值時，則快指標移動，慢指標不動，
      }
       return j;
    }
}

剛才我們學習了兩個雙指標的題目，是不是對這個做題思想有了一些理解了，下面我們來使用一個更加高級的雙指標，這個也是經常使用的思想，但是歸根結底還是雙指標思想，

該題目的思想也是雙指標的思想，不過這個代碼比較難寫一些，用到的情況也是比較多的，所以我們這個題目要用心體會一下，

209，長度最小的子陣列

給定一個含有 n 個正整數的陣列和一個正整數 s ，找出該陣列中滿足其和 ≥ s 的長度最小的 連續 子陣列，并回傳其長度，如果不存在符合條件的子陣列，回傳 0，

示例：

輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子陣列 [4,3] 是該條件下的長度最小的子陣列

題目含義比較好理解，則是在陣列里面找出長度最小的子陣列，子陣列的元素和大于等于目標值，這個題目我們就用到了滑動視窗的思想，

滑動視窗：就是通過不斷調節子陣列的起始位置和終止位置，進而得到我們想要的結果我們也可以看成是雙指標的一種，

在該題中，我們可能遇到這種情況 大家思考一下，陣列的值是1，2，3，4，5我們的s為5，所以我們第一次的子陣列（滑動視窗）長度則為3，1+2+3>5,這時左指標在1的位置，右指標在3的位置，但是2+3=5同樣符合，所以我們就需要移動左指標，此時視窗長度則改為2了，然后我們保留該值，繼續移動左指標，判斷3是否仍符合，此時發現不符合了，則需要移動右指標，移動到下一個符合情況的元素，繼續執行剛才的步驟，直到陣列的最后，所以整個程序中滑動視窗的長度變化為，3,2,3,2,3,2,1，最小的則為1.

我們可以通過以下代碼解決該題，

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int chiledlen = Integer.MAX_VALUE;
        int winlen = 0;//視窗大小
        int sum = 0;
        int i = 0;//起始長度位置
        for(int j = 0 ; j < nums.length;j++){
              sum += nums[j];
              //發現符合條件的情況
              //回圈內部的代碼是精髓所在
              while(sum>=s){
                  winlen = j-i+1;
                  chiledlen = Math.min(chiledlen,winlen);
                  //下面兩行是滑動視窗的意義所在，改變起點位置，判斷是否仍符合條件
                  sum-=nums[i];
                  i++;
              }

        }
        return chiledlen == Integer.MAX_VALUE ? 0:chiledlen;
    }
}

通過以上三個題目我們是不是對雙指標思想有了一些理解了，該思想不僅可以用在陣列的題目上，鏈表同樣適用，所以我們要完全掌握，這三個題目大家有時間的話還是自己動手做一下，