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

http://yzkb.51969.com/

文章目錄

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

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

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

例題

1.移動零

題目：移動零

樣例輸出輸入：

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

題目：復(fù)寫零

樣例輸入輸出：

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

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

class Solution

{

public:

void duplicateZeros(vector& arr)

{

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

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ù)寫操作

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.快樂數(shù)

題目：快樂數(shù)

樣例輸入輸出：

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

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

代碼展示：

class Solution {

public:

//返回n這個數(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等于第一個數(shù)

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

while(fast!=slow)

{

fast=bitsum(bitsum(fast));

slow=bitsum(slow);

}

return slow==1;

}

};

4.盛最多水的容器

題目：

樣例輸入輸出：

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

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

class Solution {

public:

//時間復(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.有效三角形的個數(shù)

題目：

輸出輸入樣例：

解法一：暴力解法 這道題的暴力解法就是就是逐個遍歷，將每一種情況遍歷一遍，這道題由于不用去重，所以復(fù)雜程度直線下降，所以我們直接用三角形的判定的公式直接逐個情況判斷就可以了，這里可以套三層循環(huán)，每種情況進行遍歷，然后如果成立的話可以直接用一個count進行記錄三角形成立的個數(shù) 解法二：雙指針 步驟1：進行排序。 步驟2：排序之后，我們可以先固定最大的數(shù)，這里我們知道三角形滿足a+b>c，這里c是最大的數(shù)，所以我們可以先固定最大的數(shù)，由于我們排序之后最大的數(shù)是最后一個數(shù)，所以這里我們可以直接取最后一個數(shù)為c，然后從c前面的數(shù)中取出a和b，但是a和b不是亂取的，我們先取最大的和最小的，也就是c前面的一個和第一個，如果最大的和最小的都能組成三角形，那么中間的組合肯定能組成三角形，因為中間的任何一個都比最小的大，所以這里可以直接計算三角形的個數(shù)的情況，三角形個數(shù)就是下標(biāo)之差，接下來還有兩種情況就是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ù)組中找三元組，并且三元組滿足三元組的每個成員都是原數(shù)組中的不同位置的數(shù)，并且三元組不能有重復(fù)，三元組還要滿足一個條件就是三元組之和加起來等于0。 解法一：暴力解法 這道題的難點就是在去重上，所以這道題我們可以用三個循環(huán)，然后把每個元素都遍歷一遍用一個vector存儲，最后把這個vector存在vectorvector中，如果是去重的話，我們可以直接用C++的一個容器就是unordered_set進行去重，最后直接把容器返回即可。

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

接下來我們來談?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ù)之和，題目也是類似，我們需要找到四個數(shù)的和等于目標(biāo)的target，但是這四個數(shù)的位置不能是一樣的，

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

解法二：雙指針 這里和三數(shù)取和類似，我們只需要固定第一個數(shù)，對后面的數(shù)進行三數(shù)求和，然后將第一個固定的數(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;

}

};

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

http://yzkb.51969.com/

好文鏈接