柚子快報(bào)邀請(qǐng)碼778899分享：基礎(chǔ)算法--雙指針?biāo)惴?/p>

http://yzkb.51969.com/

文章目錄

什么是雙指針?biāo)惴ɡ}1.移動(dòng)零2.復(fù)寫(xiě)零3.快樂(lè)數(shù)4.盛最多水的容器5.有效三角形的個(gè)數(shù)6.三數(shù)之和7.四數(shù)之和

什么是雙指針?biāo)惴?/p>

通常我們講的雙指針就是用兩個(gè)指針，兩個(gè)指針可以是快慢指針，解決成環(huán)的問(wèn)題，也可以是指向收尾的兩個(gè)指針，來(lái)減小時(shí)間復(fù)雜度。雙指針?biāo)惴ɡ锏闹羔樢膊恢故侵羔?，在?shù)組中也可以是數(shù)組元素的下標(biāo)，這里雙指針是一種思想，并不是單單指的是指針。 接下來(lái)我們用幾道例題來(lái)看看雙指針?biāo)惴ā?/p>

例題

1.移動(dòng)零

題目：移動(dòng)零

樣例輸出輸入：

這道題要我們將所有零移到數(shù)組的末尾并且不改變數(shù)組的的非零元素的相對(duì)位置，并且有一個(gè)前提就是不能開(kāi)辟新的數(shù)組，對(duì)原數(shù)組進(jìn)行操作。 解法一：暴力解法 思路：兩層循環(huán)，一層循環(huán)找零，一層循環(huán)移動(dòng)零到最后一個(gè)零的位置。 解法二：雙指針 思路：首先對(duì)于上面這個(gè)題可以這樣理解，可以把他劃分為兩個(gè)大區(qū)間，一個(gè)已經(jīng)排除過(guò)零的區(qū)間和一個(gè)未排除過(guò)零的區(qū)間，已排除過(guò)零的區(qū)間又可以劃分為非零區(qū)間和一個(gè)只含零的區(qū)間所以這三個(gè)區(qū)間。 所以我們可以用一個(gè)指針指向非零與零的區(qū)間的分界線，再用一個(gè)指針對(duì)數(shù)組進(jìn)行遍歷，如果遇到零就繼續(xù)++，因?yàn)榱惚緛?lái)就該在最后，如果遇到非零數(shù)就交換非零區(qū)間和零區(qū)間的分解線的數(shù)，這里分界線取的是第一個(gè)零的位置。這樣，當(dāng)我們遍歷到最后一個(gè)數(shù)之后，未劃分區(qū)間就沒(méi)有了，只剩下非零區(qū)間和零區(qū)間了。 代碼展示：

class Solution {

public:

void moveZeroes(vector& nums) {

int cur=0;

int dest=-1;

while(cur

{

if(nums[cur]!=0)

{

swap(nums[cur],nums[dest+1]);

dest++;

cur++;

}

else

{

cur++;

}

}

}

};

2.復(fù)寫(xiě)零

題目：復(fù)寫(xiě)零

樣例輸入輸出：

題目的意思就是讓我們把數(shù)組當(dāng)中的零在零之后復(fù)寫(xiě)但是復(fù)寫(xiě)之后數(shù)組的長(zhǎng)度不變，所以后面數(shù)向后移動(dòng)，所以最后就得到了樣例輸出。

思路： 首先我們先用異地操作模擬一下，開(kāi)辟一個(gè)新的數(shù)組，然后進(jìn)行拷貝，用兩個(gè)指針，一個(gè)指針對(duì)原來(lái)的數(shù)組進(jìn)行遍歷，一個(gè)指針對(duì)新開(kāi)辟的數(shù)組進(jìn)行遍歷，如果原來(lái)的數(shù)組遇到非零先判斷新開(kāi)辟數(shù)組是否越界，然后進(jìn)行拷貝，兩個(gè)指針同時(shí)向后移動(dòng)，如果遇到零的話，還是先判斷新開(kāi)辟的數(shù)組是否越界，如果越界就停止，如果沒(méi)越界拷貝在新開(kāi)辟的數(shù)組中拷貝兩個(gè)零，新開(kāi)辟數(shù)組的指針向后移動(dòng)兩個(gè)單位，原來(lái)的數(shù)組向后移動(dòng)一個(gè)單位。 上面講的是異地操作，我們將異地操作優(yōu)化為就地操作，首先我們考慮數(shù)組從左向右復(fù)寫(xiě)，首先這是不可能的，一個(gè)數(shù)組遍歷一個(gè)數(shù)組進(jìn)行復(fù)寫(xiě)的話會(huì)導(dǎo)致當(dāng)我們復(fù)寫(xiě)的到零的時(shí)候后面的數(shù)已經(jīng)被零覆蓋了，所以遍歷的時(shí)候后面會(huì)一直是零，復(fù)寫(xiě)就會(huì)一直復(fù)寫(xiě)零，所以這里我們考慮數(shù)組從后往前復(fù)寫(xiě)，如果從后往前復(fù)寫(xiě)的話我們就要考慮復(fù)寫(xiě)的最終位置，這里想到第一個(gè)辦法就是雙指針先就地模擬一遍異地操作，如果遇到零就+=2，如果遇到非零就+=1，這樣用兩個(gè)指針，最后一個(gè)指向末尾的元素就是就是需要拷貝的位置，另一個(gè)指針進(jìn)行遍歷數(shù)組并沒(méi)有指向最后一個(gè)位置，所以這個(gè)位置指向的是復(fù)寫(xiě)的最后一個(gè)位置。通過(guò)模擬異地的復(fù)寫(xiě)我們已經(jīng)找到最后一個(gè)復(fù)寫(xiě)的位置，現(xiàn)在只需要倒著復(fù)寫(xiě)即可，遇到零則復(fù)寫(xiě)兩邊，遇到非零則復(fù)寫(xiě)一遍。 代碼展示：

class Solution

{

public:

void duplicateZeros(vector& arr)

{

//先找到最后一個(gè)復(fù)寫(xiě)位置，模擬異地操作

int dest=-1;

int cur=0;

int n=arr.size();

while(dest

{

if(arr[cur]!=0)

{

dest++;

}

else

{

dest+=2;

}

if(dest>=n-1)break;

cur++;

}

if(dest==n)

{

arr[n-1]=0;

dest-=2;

cur-=1;

}

//從后向前完成復(fù)寫(xiě)操作

while(cur>=0)

{

if(arr[cur]!=0)

{

arr[dest--]=arr[cur--];

}

else

{

arr[dest]=arr[cur];

arr[dest-1]=arr[cur];

dest-=2;

cur-=1;

}

}

}

};

3.快樂(lè)數(shù)

題目：快樂(lè)數(shù)

樣例輸入輸出：

解法： 首先我們來(lái)看看什么事快樂(lè)數(shù)，如果各個(gè)位的平方相加，通過(guò)一系列重復(fù)操作之后，最后結(jié)果變?yōu)?，這就是快樂(lè)數(shù)，注意上面一句話很重要也就是無(wú)限循環(huán)，但可能不是1，這句話很重要。 首先我們用上面給出的兩個(gè)例子來(lái)做樣例：

上圖上面樣例的兩個(gè)例子這樣一看我們也就很熟悉了，這不是我們?cè)阪湵碜龅逆湵韼Лh(huán)的問(wèn)題嗎？判斷鏈表是否帶環(huán)只需要用一個(gè)快慢指針，如果兩個(gè)指針，最后相遇則證明有環(huán)，如果兩個(gè)指針沒(méi)有相遇則證明最后沒(méi)有環(huán)，這道題也很類似，這里的指針只需要抽象成操作的步驟，慢指針只操作一步，快指針操作兩步，上面兩種情況肯定是有環(huán)的，所以我們只需要判斷兩個(gè)指針相遇時(shí)的數(shù)是否是1，如果是1，則返回true，如果不是1，則返回false。

代碼展示：

class Solution {

public:

//返回n這個(gè)數(shù)每一位上的平方和

int bitsum(int n)

{

int sum=0;

while(n)

{

int t=n%10;

sum+=t*t;

n/=10;

}

return sum;

}

bool isHappy(int n) {

int slow=n;//slow等于第一個(gè)數(shù)

int fast=bitsum(n);//fast等于第二個(gè)數(shù)

while(fast!=slow)

{

fast=bitsum(bitsum(fast));

slow=bitsum(slow);

}

return slow==1;

}

};

4.盛最多水的容器

題目：

樣例輸入輸出：

題目意思很簡(jiǎn)單，這里的數(shù)組中的每個(gè)值代表的是高度，然后每個(gè)值對(duì)應(yīng)的下標(biāo)之差表示的是容器的寬度，寬度*高度就是我們水的最大容積。

解法一：暴力解法 暴力解法很簡(jiǎn)單，我們只需要用兩個(gè)for循環(huán)每次for循環(huán)都記錄一下這次的最大的容積，然后每次for循環(huán)完了之后，都對(duì)之前的容器的大小進(jìn)行比較，如果新的容積大則更新容積，如果新的容積小，則不動(dòng)。 解法二：雙指針?biāo)惴?首先我們先取首尾的指針，用下面的圖講解一下原理： 所以根據(jù)這個(gè)原理，向內(nèi)取的話肯定是減小，所以這里我們每次肯定是小的高度進(jìn)行–或者++。這里我們需要的變量就是兩個(gè)首尾指針，然后還有一個(gè)記錄最小值，最小值表示高度，因?yàn)楦叨仁亲钚≈禌Q定的，因?yàn)橄騼?nèi)取v是在不斷減小的，所以這里我們每次更新的時(shí)候需要更新高度小的那個(gè)，更新高度大的那個(gè)會(huì)出現(xiàn)的情況可以看上面的圖。 代碼展示：

class Solution {

public:

//時(shí)間復(fù)雜度是O(N)

int maxArea(vector& height) {

int tail=height.size()-1;

int head=0;

int v=0;

while(head

{

int Min=min(height[head],height[tail]);

if(v

{

v=Min*(tail-head);

}

if(height[tail]

{

tail--;

}

else

{

head++;

}

}

return v;

}

};

5.有效三角形的個(gè)數(shù)

題目：

輸出輸入樣例：

解法一：暴力解法 這道題的暴力解法就是就是逐個(gè)遍歷，將每一種情況遍歷一遍，這道題由于不用去重，所以復(fù)雜程度直線下降，所以我們直接用三角形的判定的公式直接逐個(gè)情況判斷就可以了，這里可以套三層循環(huán)，每種情況進(jìn)行遍歷，然后如果成立的話可以直接用一個(gè)count進(jìn)行記錄三角形成立的個(gè)數(shù) 解法二：雙指針 步驟1：進(jìn)行排序。 步驟2：排序之后，我們可以先固定最大的數(shù)，這里我們知道三角形滿足a+b>c，這里c是最大的數(shù)，所以我們可以先固定最大的數(shù)，由于我們排序之后最大的數(shù)是最后一個(gè)數(shù)，所以這里我們可以直接取最后一個(gè)數(shù)為c，然后從c前面的數(shù)中取出a和b，但是a和b不是亂取的，我們先取最大的和最小的，也就是c前面的一個(gè)和第一個(gè)，如果最大的和最小的都能組成三角形，那么中間的組合肯定能組成三角形，因?yàn)橹虚g的任何一個(gè)都比最小的大，所以這里可以直接計(jì)算三角形的個(gè)數(shù)的情況，三角形個(gè)數(shù)就是下標(biāo)之差，接下來(lái)還有兩種情況就是a+b==c或者a+b

class Solution

{

public:

int triangleNumber(vector& nums)

{

sort(nums.begin(),nums.end());

int count=0;

int left=0;

int right=nums.size()-2;

int c=nums.size()-1;

while(c>=2)

{

while(left

{

if(nums[left]+nums[right]>nums[c])

{

count+=(right-left);

right--;

}

else

{

left++;

}

}

//更新right和left

c--;

left=0;

right=c-1;

}

return count;

}

};

6.三數(shù)之和

題目：

樣例輸出和輸入：

這里我們可以直接看樣例，題目的大概意思就是我們需要從數(shù)組中找三元組，并且三元組滿足三元組的每個(gè)成員都是原數(shù)組中的不同位置的數(shù)，并且三元組不能有重復(fù)，三元組還要滿足一個(gè)條件就是三元組之和加起來(lái)等于0。 解法一：暴力解法 這道題的難點(diǎn)就是在去重上，所以這道題我們可以用三個(gè)循環(huán)，然后把每個(gè)元素都遍歷一遍用一個(gè)vector存儲(chǔ)，最后把這個(gè)vector存在vectorvector中，如果是去重的話，我們可以直接用C++的一個(gè)容器就是unordered_set進(jìn)行去重，最后直接把容器返回即可。

解法二：雙指針 這里雙指針和上一道題的雙指針類似，還是需要固定一個(gè)數(shù)，這道題我們不用unordered_set進(jìn)行去重，因?yàn)樵谒惴}中可以用，但是在面試題中用unordered_set很可能會(huì)掛掉，所以我們海獅正常的用算法進(jìn)行去重，首先我們海獅先排序，排序可以把相同的元素排在一起，排完序之后先固定一個(gè)數(shù)，我們先固定首元素，然后對(duì)首元素后面的數(shù)進(jìn)行遍歷，這里遍歷只需要取首尾元素，這道題三數(shù)之和我們就轉(zhuǎn)化為了兩數(shù)之和，我們只需要求后面區(qū)間的數(shù)中存在兩個(gè)數(shù)加起來(lái)等于前面這個(gè)數(shù)的相反數(shù)的組合即可，如果存在，則將其入到vector中，如果不存在則繼續(xù)遍歷，將固定的那個(gè)數(shù)往后移動(dòng)，這里我們需要注意的細(xì)節(jié)是：我們后面的數(shù)加起來(lái)有三種情況： 第一種：大于前面的數(shù)，如果大于前面的數(shù)，可以直接將最大數(shù)–，因?yàn)檫@個(gè)數(shù)組被我們排成有序的了，所以不可能用left++，left++只會(huì)更大，所以應(yīng)該是right–。 第二種情況：left+right=-a，這個(gè)情況直接入到數(shù)組中。 第三種情況：；left+right<-a，如果小于這個(gè)數(shù)，left++，如果right–只會(huì)更小。

接下來(lái)我們來(lái)談?wù)勅ブ氐牟僮鳎? 代碼展示：

class Solution

{

public:

vector> v;

vector> threeSum(vector& nums)

{

sort(nums.begin(), nums.end());

int i = 0;

while (i <= nums.size() - 2)

{

int left = i + 1;

int right = nums.size() - 1;

while (left < right)

{

vector ret;

int ret1 = nums[left];

int ret2 = nums[right];

if (nums[left] + nums[right] == -nums[i])

{

ret.push_back(nums[left]);

ret.push_back(nums[right]);

ret.push_back(nums[i]);

v.push_back(ret);

}

if (nums[left] + nums[right] < -nums[i])

{

while (nums[left] == ret1)

{

left++;

if (left >= right)

{

break;

}

}

}

else

{

while (nums[right] == ret2)

{

right--;

if (left >= right)

{

break;

}

}

}

}

int j = nums[i];

while (nums[i] == j)

{

i++;

if (i > nums.size() - 1)

{

break;

}

}

}

return v;

}

};

7.四數(shù)之和

題目：

輸出樣例和輸入樣例：

四數(shù)之和可以參照三數(shù)之和，題目也是類似，我們需要找到四個(gè)數(shù)的和等于目標(biāo)的target，但是這四個(gè)數(shù)的位置不能是一樣的，

解法一：暴力解法 暴力解法很簡(jiǎn)單，只需要用四層循環(huán)把每種情況進(jìn)行遍歷一遍即可，最后再用容器進(jìn)行去重操作。

解法二：雙指針 這里和三數(shù)取和類似，我們只需要固定第一個(gè)數(shù)，對(duì)后面的數(shù)進(jìn)行三數(shù)求和，然后將第一個(gè)固定的數(shù)逐漸往后遍歷即可。

代碼展示：

class Solution

{

public:

vector> v;

vector> fourSum(vector& nums, int target)

{

vector> ret;

//排序

int n=nums.size();

sort(nums.begin(),nums.end());

for(int i=0;i

{

for(int j=i+1;j

{

int left=j+1,right=n-1;

long long aim=(long long)target-nums[i]-nums[j];

while(left

{

int sum=nums[left]+nums[right];

if(sum

else if(sum>aim)right--;

else

{

ret.push_back({nums[left++],nums[right--],nums[i],nums[j]});

//nums和nums的去重

while(left

while(left

}

}

j++;

while(j

}

i++;

while(i

}

return ret;

}

};

柚子快報(bào)邀請(qǐng)碼778899分享：基礎(chǔ)算法--雙指針?biāo)惴?/p>

http://yzkb.51969.com/

好文鏈接