雙指標
同向雙指標
能夠實作跳躍尋找，適用于尋找含有某一特性區間，比如最長相同區間，最長不重復區間
不重復區間可以用一個陣列t[N]來表示，如果其中元素大于1，說明有重復
int res=0,j=0;
for(int i=0;i<n;i++)
{
t[a[i]]++;//記錄個數
while(j<i&&t[a[i]]>1) t[a[j++]]--;//改變區間
if(i-j+1>res) res=i-j+1;
}
相同區間用第二個指標移動來尋找下一個不相同的位置，可計算出區間長度
int num=0;
char ans;
for(int i=0;i<s.size();)
{
int j=i;
while(j<s.size()&&s[j]==s[i]) j++;
if(j-i>num) num=j-i,ans=s[i];
i=j;
}
雙向雙指標
一個從前往后走，一個從后往前走
使得與暴力回圈兩個陣列不同的是，j不會回退
例子:給定兩個升序排序的有序陣列 A 和 B，以及一個目標值 x，
for (int i = 0, j = m - 1; i < n; i ++) {
while(j >= 0 && a[i] + b[j] > k) j --;
if(j >= 0 && a[i] + b[j] == k) printf("%d %d\n", i, j);
}
中向雙指標
兩個指標從左右兩側開始移動直到相遇
例：快速排序中根據軸值劃分，調整奇偶序列，翻轉陣列
while(i<j) //未相遇繼續回圈
{
while(state) i++;
while(state) j--;
if(i<j) swap(x,y);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/545821.html
標籤：C++
上一篇：Hello，Golang