双指针

1.双指针理论部分

双指针是一个常用的优化技巧，是一种通过设置两个指针不断进行单向移动用来解决序列的区间问题

两个指针，有两种扫描方向：

1. 同向扫描(快慢指针)：方向相同，都从头到尾，一个走的慢，一个走快
2. 反向扫描:方向相反，一个从头到尾，一个从尾到头，在中间相会

双指针的核心：找单调关系：和的之间关系

(1)如何判断一个题目是否可以用双指针来解

1. 因为双指针算法是一种优化时间复杂度的方法，所以我们可以首先写出最朴素的两层循环的写法。

2. 然后考虑题目中是否具有单调性。

即当其中一个指针向后移动时，在希望得到答案的情况下，另一个指针是不是只能向着一个方向移动。

3. 如果是，说明题目具有单调性，可以通过双指针算法优化。

(2)双指针模板

for(int i=0,j=0;i<n;i++){
    while(j<i&&check(i,j)) j++;
    //每道题目具体逻辑
}

2.双指针题目题解

(1).最长连续不重复子序列 

题意

给定一个长度为 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度

解题思路

假设区间是以为终点的最长连续不重复子序列

不难发现，若向后移动()，只会向后或不移动，不可能往前移动

证明如下：

假设 是以 为终点的最长连续不重复子序列。如果当 向后移动时(比如到 )，却向前移动了(比如到 )。 说明 是以 为终点的最长连续不重复子序列，换句话说： 范围内都没有重复元素。 即：以 为终点的最长连续不重复子序列应该是 而不是 ，与假设相矛盾 因此可证明： 当向后移动时，不可能向前移动 （可能不动，也可以向后，就是不可能向前）

由此我们可以用双指针在时间复杂度解决该问题

解题代码

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n),num(100010,0);
    for(int i=0;i<n;i++) cin>>a[i];
    int res=0;
    for(int j=0,i=0;i<n;i++){
        num[a[i]]++;
        while(j<i&&num[a[i]]>1) num[a[j]]--,j++;
        res=max(res,i-j+1);
    }
    cout<<res<<"\n";
}

int main()
{
    solve();
    return 0;
}

(2).Xor Sum 2

题意

给定一数组，求出满足的的数量

解题思路

假设为满足题意的最大区间：满足

当增大时，则有，由于异或和是不进位的加法，有，只有增大才能使得

原因：当减小()时，根据性质，恒成立

解题代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
  int n;
  cin>>n;
  vector<ll> a(n+1);
  for(int i=1;i<=n;i++) cin>>a[i];
  ll sum=0,x=0;
  ll res=0;
  for(int i=1,j=0;i<=n;i++){
    while(j+1<=n&&sum+a[j+1]==(x^a[j+1])){
      j++;
      sum+=a[j];
      x^=a[j];
    }
    res+=j-i+1;
    sum-=a[i];
    x^=a[i];
  }
  cout<<res<<"\n";
}

int main()
{
  solve();
}

(3).连续自然数和 

题意

对一个给定的正整数 M，求出所有的连续的正整数段（每一段至少有两个数），这些连续的自然数段中的全部数之和为 M。

解题思路

假设为满足连续自然数之和的区间，则当增大时，则有该连续自然数之和

• 当减小时，增大，恒成立

• 当增大时，减小，可能成立

因此随着的增大而增大，满足单调性，可以使用双指针算法解决此题

解题代码

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int m;
    cin>>m;
    int sum=0;
    for(int l=1,r=1;r<m;r++){
        sum+=r;
        while(l<r&&sum>m){
            sum-=l,l++;
        }
        if(sum==m) 
            cout<<l<<" "<<r<<"\n";
    }
}

int main()
{
    solve();
    return 0;
}