呀哈嘍，我是結衣。
對于要參加程序設計比賽的人來說，算法永遠都是一道繞不開的坎，你必須的去了解他才可以更好的去解決問題。非形式地說，算法就是任何良地計算過程，我們可以把算法看作是用于求良說明地計算問題地工具。那么今天我們學到的就是其中最基礎的一種，雙指針的應用。
在今天的這篇文章，我們將會了解到雙指針的絕大多數(shù)題型，掌握了他們，那么你的雙指針就算是過關了。文章的題目都是由易到難。在看完解題方法后請先自己敲出代碼后再考代碼部分哦。
0.雙指針的介紹
常?的雙指針有兩種形式，?種是對撞指針，?種是左右指針。
對撞指針：?般?于順序結構中，也稱左右指針。
對撞指針從兩端向中間移動。?個指針從最左端開始，另?個從最右端開始，然后逐漸往中間逼
近。
對撞指針的終?條件?般是兩個指針相遇或者錯開（也可能在循環(huán)內(nèi)部找到結果直接跳出循
環(huán)），也就是：
left == right（兩個指針指向同?個位置）
left > right （兩個指針錯開）
快慢指針：?稱為?兔賽跑算法，其基本思想就是使?兩個移動速度不同的指針在數(shù)組或鏈表等序列
結構上移動。
這種?法對于處理環(huán)形鏈表或數(shù)組?常有?。
其實不單單是環(huán)形鏈表或者是數(shù)組，如果我們要研究的問題出現(xiàn)循環(huán)往復的情況時，均可考慮使?快
慢指針的思想。
快慢指針的實現(xiàn)?式有很多種，最常?的?種就是：
在?次循環(huán)中，每次讓慢的指針向后移動?位，?快的指針往后移動兩位，實現(xiàn)?快?慢。
1.移動零（easy）
題目鏈接：移動零
題目描述：
思路
當我們遇到這種需要將數(shù)組分為兩個模塊的時候，我們就可以考慮使用雙指針來解決問題。
解決方法
我們用cur指針去掃描整個數(shù)組，另一個指針dest去指向cur前最后一個0的位置，每當cur指向非零元素時就交換dest和cur指向的數(shù)。
利用這個方法我們就可以把[0,dest]的元素全都轉化為非0元素，[dest+1,cur-1]的元素全為0.
了解完方法后先嘗試著把代碼寫出來吧。
代碼
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int dest = -1,cur = 0;
while(cur<nums.size())
{
if(nums[cur]!=0)
{
swap(nums[dest+1],nums[cur]);
++dest;++cur;
}
else
++cur;
}
}
};
當然這題也可以用暴力寫出來，不過暴力的時間復雜度就很高了為O(N^2)。所以我們還有用雙指針來解決問題吧。
2.復寫零（easy）
題目鏈接：復寫零
題目描述：
思路
對數(shù)組的就地操作，嘗試雙指針看看。
解題方法
可題目要求我們就地修改。為了符合題意，我們要把cur和dest同時指向arr數(shù)組。如果我們重復上述的操作，在arr數(shù)組中進行就會發(fā)現(xiàn)，會存在數(shù)據(jù)的覆蓋。
2被覆蓋掉了。
那么我們要如何避免這種情況呢？既然從前向后掃描不行，那我們從后向前呢？
我們從dest和cur會停留的地方開始向前掃描。
規(guī)則和前向后一樣，可是后向前并不會覆蓋掉數(shù)字。了解到這樣步，這道題就解決了一半，為什么呢？因為我們還不知道cur和dest最后的位置。為了求到他們最后的位置，我們還要去運用一次雙指針。
這次我們從前向后，cur掃描數(shù)組，如果cur指向數(shù)為0，dest+=2，不為0dest+=1.因為cur無論怎樣都要加，所有我們把它放在最后加。同時，當dest指向最后一個位置時就退出循環(huán)。但是！在這種要求下會有一些特殊情況，會讓dest指向數(shù)組外。當數(shù)組為[1,0,2,3,1,0,4,0]時，dest會出數(shù)組。
為此我們就需要在后續(xù)加一些判斷條件，當發(fā)生這種情況時，我們直接讓arr[n-1] = 0;dest-=2;cur–;
代碼
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int n = arr.size();
int dest = -1,cur = 0;
while(cur<n)
{
if(arr[cur] == 0)dest+=2;
else dest+=1;
if(dest>=n-1)break;
cur++;
}
if(dest == n)
{
dest--;
arr[dest--] = 0;
cur--;
}
while(cur>=0)
{
if(arr[cur] != 0)
{
arr[dest--] = arr[cur];
}
else
{
arr[dest--] = 0;
arr[dest--] = 0;
}
cur--;
}
}
};
3.快樂數(shù)（easy）
題目鏈接：快樂數(shù)
題目描述：
思路
運用鴿巢原理（抽屜原理）了解到了解到平方和最后一定會形成一個環(huán)，考慮快慢指針。
解題方法
鴿巢原理（抽屜原理）：桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發(fā)現(xiàn)至少會有一個抽屜里面放不少于兩個蘋果。這一現(xiàn)象就是我們所說的“抽屜原理”。比如當我們?nèi)∫粋€較大數(shù)，9999999999，他的各位的平方和位810.遠小于他本身，同時這也是100億內(nèi)最大的各位平方和。由這個原理，我們就會知道只要循環(huán)了811個數(shù)，就一定會由重復的數(shù)出現(xiàn)然后形成一個環(huán)
當然我們也可以把1當成循環(huán)
如此一來，快慢指針就發(fā)揮作用了，我們讓fast指針一次走兩個位置，slow指針一次走一個位置，那么可以預見的是，fast一定會先進入到環(huán)當中，當slow進入環(huán)時，fast也在環(huán)中，又因為fast速度更快，那么fast就一定會和slow相遇，我們只需要判斷他們相遇的點是否為1就可以了。
復雜度
時間復雜度: O ( n ) O(n) O(n)
空間復雜度: O ( 1 ) O(1) O(1)
代碼
class Solution {
public:
int f(int x)
{
int sum = 0;
while(x)
{
sum+=pow(x%10,2);
x = x/10;
}
return sum;
}
bool isHappy(int n) {
int fast = n,slow = n;
while(1)
{
fast = f(f(fast));
slow = f(slow);
if(fast == slow&&fast == 1)
return true;
if(fast == slow&&fast!=1)
return false;
}
return false;//因為判斷已經(jīng)在循環(huán)中完成了，這里隨便返回一個就可以了。
}
};
4.盛水最多的容器（medium）
題目鏈接：盛水最多的容器
題目描述：
思路
因為水的面積取決于長乘寬，而長又取決于短的一邊。由此我們可以得出假設先以數(shù)組的兩邊為長，再移動左右的長是具有一定的單調(diào)性的。
解題方法
我們以示例1為例：
我們先以兩端為長，面積為1*8=8
然后我們要移動哪一個呢？如果我們移動較大的一段7
就會發(fā)現(xiàn)，面積絕對是變小的，因為，寬在減小，而長一定不會大于1
所以我們會移動較小的一端，直到他們相遇
左右指針，就是這題的解法。
復雜度
時間復雜度: O ( n ) O(n) O(n)
空間復雜度: O ( 1 ) O(1) O(1)
代碼
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0,right = height.size()-1;
int sum = 0;
while(left<right)
{
if(height[left]<height[right])
{
sum = max(sum,height[left]*(right-left));
left++;
}
else
{
sum = max(sum,height[right]*(right-left));
right--;
}
}
return sum;
}
};
5.有效的三角形個數(shù)（medium）
題目鏈接：有效的三角形個數(shù)
題目描述：
思路
三角形的任意兩條邊大于第3條邊。（進階）當已知a<=b<=c時我們只要判斷a+b>c就可以了
解題方法
當我們知道進階方法后，我們就要給數(shù)組排個序了，然后利用雙指針來解決問題。
我們只需要將數(shù)組排序，然后先固定cur在數(shù)組的最大位置上。
判斷l(xiāng)eft+right是否會大于cur，如果會大于cur，那么當left等于中間任何數(shù)時
都會大于cur，因為數(shù)組是遞增的。我們把right–就可以了
如果left+right<=cur，我們就要left++，來找后續(xù)合適的數(shù)了。
當我們遍歷完一輪后（left<=right）
我們要–cur，然后重新分配left和right
直到cur<2,就結束
復雜度
時間復雜度: O ( n 2 + n ? l o g n ) O(n^2+n*logn) O(n2+n?logn)
空間復雜度: O ( 1 ) O(1) O(1)
代碼
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int n = nums.size();
if(n<3)
return 0;
sort(nums.begin(),nums.end());
int a = 0,b = n-2,c = n-1;
int res = 0;
while(c>=2)
{
a = 0;b = c-1;
while(a<b)
{
if(nums[a]+nums[b]>nums[c])
{
res+=b-a;
b--;
}
else a++;
}
c--;
}
return res;
}
};
6.查找總價格為目標值的兩個商品（easy）
題目鏈接：查找總價格為目標值的兩個商品
題目描述：
思路
利用左右指針向中間掃描
解題方法
因為題目數(shù)組已經(jīng)排好了序，也省去了我們排序的時間，要解決這類問題最關鍵的就是數(shù)組是要有序的，有序的數(shù)組可以幫我們解決很多的問題。
就那這題來說
如果le+ri大于18，那么我們肯定就要把right–啦
數(shù)組是遞增的，++left只會增加le+ri。
如果le+ri小于18，我們就要把left++
道理和上面相似。
然后我們只需要重復這個過程直到找到＝tar為止
但是要注意的是因為我們一定會在循環(huán)內(nèi)找到tar，但是外面也是一個返回值要不然不會讓你編譯成功，所以我們隨便返回一個就是了
復雜度
時間復雜度: O ( n ) O(n) O(n)
空間復雜度: O ( 1 ) O(1) O(1)
代碼
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int n = price.size();
int left = 0,right = n-1;
while(left<right)
{
if(price[left]+price[right]>target) right--;
else if(price[left]+price[right]<target) left++;
else
return {price[left],price[right]};
}
return {-1,-1};//但是要注意的是因為我們一定會在循環(huán)內(nèi)找到tar，但是外面也是一個返回值要不然不會讓你編譯成功，所以我們隨便返回一個就是了
}
};
7.三數(shù)之和（medium）
題目鏈接：三數(shù)之和
題目描述：
思路
由三數(shù)之和想到，固定一個數(shù)然后求數(shù)組除去這個數(shù)后的兩數(shù)之和為目標值。同時注意去重，以及邊界問題.
解題方法
我們先給數(shù)組排序，為了方便固定數(shù)同時也方便求兩數(shù)之和。
內(nèi)部求兩數(shù)之和為特定值的方法和查找總價格為目標值的兩個商品類似，但是我要考慮去重的問題，以及我們現(xiàn)在不止找以組數(shù)據(jù)，所以當我找到了一組數(shù)據(jù)時，先考慮去重的問題，
這里是會存在邊界問題的，如果left跑到了數(shù)組之外怎么辦，所以我們要加個left<right來限制。
考慮完里面后我們就要來到外面了，當里面判斷完了后，我們的cur也該換位置了，我們可以往后移動一格，但是去重的問題同樣要解決，所以我們可以用和上面一樣的辦法來解決，但是對于邊界問題我們就要讓cur<n-1了。因為如果cur<n后面的nums[cur+1]就會由越界的可能。
復雜度
時間復雜度: O ( n 2 ) O(n^2) O(n2)
空間復雜度: O ( 1 ) O(1) O(1)
代碼
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
if(nums[0]>0)
return res;
int cur = 0;
int n = nums.size();
while(cur<n&&nums[cur]<=0)
{
int left = cur+1,right = n-1;
vector<int> tmp(3);
while(left<right)
{
if(nums[left]+nums[right] > -nums[cur]) right--;
else if(nums[left]+nums[right] < -nums[cur]) left++;
else
{
tmp[0] = nums[cur];
tmp[1] = nums[left];
tmp[2] = nums[right];
res.push_back(tmp);
while(left<right&&nums[left]==nums[left+1])
left++;
if(left<right)
left++;
}
}
while(cur<n-1&&nums[cur]==nums[cur+1])
cur++;
//if(nums[cur]<=0)*/
cur++;
}
return res;
}
};
8.四數(shù)之和（medium）
題目鏈接：四數(shù)之和
題目描述：
思路
思路和三數(shù)之和完全類型，我們要先把四數(shù)之和轉化為三數(shù)之和，然后再轉化為兩數(shù)之和為目標值的問題。
解題方法
具體的解釋完全可以參考三數(shù)之和，我們只需要再套一個循環(huán)來再固定一個值就可以了。
方法就是如此，這題最重要的還是邊界問題，和上一題三數(shù)之和一樣處理就可以了。
不過在提交之后你會遇到一個ex的例子。
沒錯你要考慮一下溢出的問題。
復雜度
時間復雜度: O ( n 3 ) O(n^3) O(n3)
空間復雜度: O ( 1 ) O(1) O(1)
代碼
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
int cur = 0;
int n = nums.size();
int prev = 0;
while(prev<n)
{
long long target_2 = target - nums[prev];
cur = prev+1;
while(cur<n)
{
int left = cur+1,right = n-1;
while(left<right)
{
long long target_3 = target_2 - nums[cur];
if(nums[left]+nums[right] > target_3) right--;
else if(nums[left]+nums[right] < target_3) left++;
else
{
res.push_back({nums[prev],nums[cur],nums[left],nums[right]});
while(left<right&&nums[left]==nums[left+1])
left++;
if(left<right)
left++;
}
}
while(cur<n-1&&nums[cur]==nums[cur+1])
cur++;
cur++;
}
while(prev<n-1&&nums[prev]==nums[prev+1])
prev++;
prev++;
}
return res;
}
};
總結
提供這八個題目，你了解到了雙指針的奧秘了嗎？對于一些簡單的題目，我們也許只需要定義兩個指針一起向后跑就可以了，如果這兩個指針在跑的過程中會出現(xiàn)覆蓋的現(xiàn)象我們就要考慮從后向前來掃描數(shù)組了。當我們遇到成環(huán)的問題快慢指針來幫忙。再就是遇到要考慮單調(diào)性問題的時候，我們就可以先排序，然后再利用左右指針（對撞指針）最后就是求幾個數(shù)之和為目標值之和的問題，我們同樣是先排序然后在把這個問題依次降為求2個數(shù)之和為目標值的問題。
最后如果發(fā)現(xiàn)文章錯誤地方希望得到您的指正文章來源：http://www.zghlxwxcb.cn/news/detail-825984.html
完文章來源地址http://www.zghlxwxcb.cn/news/detail-825984.html
到了這里，關于假期算法提升（一篇文章帶你徹底學會雙指針）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
