双指针算法

最长连续不重复子序列

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

核心思路

遍历数组a中的每一个元素a[i], 对于每一个i，找到j使得双指针[j, i]维护的是以a[i]结尾的最长连续不重复子序列，长度为i - j + 1, 将这一长度与r的较大者更新给r。
对于每一个i，如何确定j的位置：由于[j, i - 1]是前一步得到的最长连续不重复子序列，所以如果[j, i]中有重复元素，一定是a[i]，因此右移j直到a[i]不重复为止（由于[j, i - 1]已经是前一步的最优解，此时j只可能右移以剔除重复元素a[i]，不可能左移增加元素，因此，j具有“单调性”、本题可用双指针降低复杂度）。
用数组s记录子序列a[j ~ i]中各元素出现次数，遍历过程中对于每一个i有四步操作：cin元素a[i] -> 将a[i]出现次数s[a[i]]加1 -> 若a[i]重复则右移j（s[a[j]]要减1） -> 确定j及更新当前长度i - j + 1给r。

#include <iostream>

using namespace std;
const int N = 1e5 + 10;

int n;
int a[N], s[N];

int main()
{
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  int res = 0;
  for(int i = 0, j = 0; i < n; i++)
  {
    s[a[i]]++;
    while( s[a[i]] > 1 )
    {
      s[a[j]]--;
      j++;
    }
    res = max(res, i - j + 1);
  }
  cout << res << endl;
  
  return 0;
}

数组元素的目标和

给定两个升序排序的有序数组 A 和 B，以及一个目标值 X。

数组下标从 0 开始。

请你求出满足A[i] + B[j] = X的数对(i, j)。

数据保证有唯一解。

解法

此题有多种解法，这里主要描述使用双指针算法来解此题。

我们可以简化一下问题，变成求 A_i + B_j \geq x 且 j 要最小。

我们用一个指针 i 枚举 A 中所有的数，而 j 则用来枚举 B ，但由于数组是单调递增的，所以如果 A_i + B_j \geq x 那么 B_{\text{j+1}} 到 B_m 就不可能是答案。

所以 j 是只能递减的，如此，我们就可以用 O(n + m) 的时间复杂度通过这道题。

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];

int main()
{
  int n, m, x;
  cin >> n >> m >> x;
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < m; i++) cin >> b[i];
  
  
  for(int i = 0, j = m - 1; i < n; i++)
  {
    while( j >= 0 && a[i] + b[j] > x )j--;
    if( a[i] + b[j] == x )cout << i << " " << j;
  }
  
  return 0;
}

判断子序列

给定一个长度为 n 的整数序列 a_1,a_2,...a_n 以及一个长度为 m 的整数序列 b_1,b_2,...,b_m 。

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 \{ a_1, a_3, a_5 \} 是 \{a_1,a_2,a_3,a_4,a_5\} 的一个子序列。

1.j指针用来扫描整个b数组，i指针用来扫描a数组。若发现a[i] == b[j]，则让i指针后移一位。

2.整个过程中，j指针不断后移，而i指针只有当匹配成功时才后移一位，若最后若i == n，则说明匹配成功。

为什么双指针做法是正确的？

整个过程中j指针不断扫描b数组并且向后移动，相当于不断给i指针所指向的a数组创建匹配的机会，只有匹配成功时i指针才会向后移动一位，当i == n时，说明全部匹配成功。

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;

int main()
{
  cin >> n >> m;
  for(int i = 0; i < n; i++)cin >> a[i];
  for(int i = 0; i < m; i++)cin >> b[i];
  
  int i = 0, j = 0;
  for(; i < m && j < n;)
  {
    if( b[i] == a[j] )j++;
    i++;
  }
  if( j == n )cout << "Yes";
  else cout << "No";
  return 0;
}