那些可以用雙指針解決的題目

• 什么時(shí)候用雙指針，該咋用？
• • 雙指針?biāo)æž·?/li>
  • • 35.搜索插入位置
    • 27.移除元素
    • 209，長度最小的子數(shù)組

什么時(shí)候用雙指針，該咋用？

雙指針?biāo)枷?/h2>

雙指針是我們做題中經(jÄ«ng)常用到的思想，所以這個(gè)在刷題初期是一定要會(huì)的。其實(shí)我們早就學(xué)ç¿’(xí)過這個(gè)方法，我們通過二分查找來描述一下這個(gè)思想。

二分查找首先定義兩個(gè)指針，左指針和右指針，分別指向數(shù)組的頭和尾，然后計(jì)算出他倆的中間的索引，其值和目標(biāo)值進(jìn)行比較，如果目標(biāo)值更大則說明目標(biāo)值在中間索引和右指針中間，則需要移動(dòng)左指針到中間索引的后一位。如果目標(biāo)值比中間值小，則需要移動(dòng)右指針到中間索引的前一位。不斷執(zhí)è¡Œ，直至找到目標(biāo)值，或當(dāng)該數(shù)組不含有目標(biāo)值，左指針和右指針重合時(shí)跳出該循環(huán)。

二分查找代碼

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

35.搜索插入位置

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置。你可以假設(shè)數(shù)組中無重復(fù)元素。

示例 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是不太容易的。我們根據(jù)題意可以想到，這樣共有四種可能

插入情況無非就這幾種

（1）比數(shù)組里的任何值都小，插入頭部

（2）比數(shù)組里的任何值都大，插入尾部

（3）查詢到數(shù)組元素，返回該處索引值

（4）數(shù)組內(nèi)無該元素，將其插入兩元素之間。

所以我們可以通過以下代碼實(shí)現(xiàn)該題

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;
            //移動(dòng)左指針
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                //移動(dòng)右指針
                right = mid - 1;
            }
        }
        //1，2，4三種情況都在循環(huán)å…§(nèi)部，我們只需輸出左指針即可。
        return left;
    }
}

---

剛才我們說了雙指針?biāo)枷氲闹匾?#xff0c;下面這個(gè)題目也是可以完全通過雙指針?biāo)枷雽?shí)現(xiàn)çš„，所以說雙指針的思想是必須有的。你可以通過下面這個(gè)題目完全體會(huì)到雙指針的重要性

27.移除元素

給你一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。

不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。

元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。

示例 1:

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

函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個(gè)元素均為 2。

你不需要考慮數(shù)組中超出新長度后面的元素。

示例 2:

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

函數(shù)應(yīng)該返回新的長度 5, 并且 nums 中的前五個(gè)元素為 0, 1, 3, 0, 4。

注意這五個(gè)元素可為任意順序。

你不需要考慮數(shù)組中超出新長度后面的元素。

該題目我們可以創(chuàng)建兩個(gè)指針，一前一后，前面的負(fù)責(zé)探路后面的負(fù)責(zé)å¡«å……，當(dāng)前面查詢到需要移除的元素時(shí)直接跳過該元素，繼續(xù)前進(jìn)。后面的指針只負(fù)責(zé)往該數(shù)組里面填充不需要移除的數(shù)å­—。所以我們可以根據(jù)以下代碼實(shí)現(xiàn)

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++;
          }
          //如果為需要?jiÇŽng)h除的值時(shí)，則快指針移動(dòng)，慢指針不動(dòng)。
      }
       return j;
    }
}

---

剛才我們學(xué)ç¿’(xí)了兩個(gè)雙指針的題目，是不是對這個(gè)做題思想有了一些理解了，下面我們來使用一個(gè)更加高級的雙指針，這個(gè)也是經(jÄ«ng)常使用的思想，但是歸根結(jié)底還是雙指針?biāo)枷搿?/p>

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

209，長度最小的子數(shù)組

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的 連續(xù) 子數(shù)組，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0。

示例：

輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組

題目含義比較好理解，則是在數(shù)組里面找出長度最小的子數(shù)組，子數(shù)組的元素和大于等于目標(biāo)值。這個(gè)題目我們就用到了滑動(dòng)窗口的思想。

滑動(dòng)窗口：就是通過不斷調(diào)節(jié)子數(shù)組的起始位置和終止位置，進(jìn)而得到我們想要的結(jié)果我們也可以看成是雙指針的一種。

在該題中，我們可能遇到這種情況 大家思考一下，數(shù)組的值是1，2，3，4，5我們的s為5，所以我們第一次的子數(shù)組（滑動(dòng)窗口）長度則為3，1+2+3>5,這時(shí)左指針在1的位置，右指針在3的位置，但是2+3=5同樣符合，所以我們就需要移動(dòng)左指針，此時(shí)窗口長度則改為2了。然后我們保留該值，繼續(xù)移動(dòng)左指針，判斷3是否仍符合，此時(shí)發(fā)現(xiàn)不符合了，則需要移動(dòng)右指針，移動(dòng)到下一個(gè)符合情況的元素，繼續(xù)執(zhí)行剛才的步驟，直到數(shù)組的最后。所以整個(gè)過程中滑動(dòng)窗口的長度變化為，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];
              //發(fā)現(xiàn)符合條件的情況
              //循環(huán)內(nèi)部的代碼是精髓所在
              while(sum>=s){
                  winlen = j-i+1;
                  chiledlen = Math.min(chiledlen,winlen);
                  //下面兩行是滑動(dòng)窗口的意義所在，改變起點(diÇŽn)位置，判斷是否仍符合條件
                  sum-=nums[i];
                  i++;
              }

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

通過以上三個(gè)題目我們是不是對雙指針?biāo)枷胗辛艘恍├斫饬?#xff0c;該思想不僅可以用在數(shù)組的題目上，鏈表同樣適用。所以我們要完全掌握，這三個(gè)題目大家有時(shí)間的話還是自己動(dòng)手做一下。

---