双指针算法的实现

思路：
暴力法：
当然可以用暴力法：对每个 i 和 j 都遍历一遍，对每个 i 和 j 都check一下中间的数据是否满足给定的条件。这样的时间复杂度是O(n^2)；数据稍微大点就会超时。
代码如下：

for (int i = 0; i < n; i++)
    for (int j = 0; j <= i; j++)
        if (check(v1,j, i) == 0)//检查 i 和 j 之间是否有重复的数字
            res = max(res, i - j + 1);
1
2
3
4

//check函数
int check(vector& v1, int l, int r)
{
for (int i = l+1; i <=r ; i++)
for (int j = l; j < i; j++)
if (v1[i] == v1[j])
return 1;
return 0;
}

双指针法一：
仔细考虑暴力法就会发现，暴力法在解题时有很多地方是重复计算了 ( i 指针在 j 指针的后面，i是遍历的整个数组的，j 是遍历 0 到 i 的)：

比如 j = 0，i = 5，此时发现 i，j 是满足题解条件的；那么后面的 j = 1到5，i = 5 就不用计算了，肯定是满足条件的。

所以引出了双指针法：还是上面的例子，双指针法就是说，既然发现 j = 0，i = 5满足题解条件，那就不用计算 j = 1到5，i = 5了，直接计算 j = 1，i = 6，如果不满足条件，那就计算 j = 2，i = 6，然后接着计算。

这样就是 i 和 j 指针都是从前移到后，也就是计算2n次。时间复杂度是O(2n)。

核心代码如下：（但是还会超时）。

for (int i = 0, j = 0; i < n; i++)
{
    while (j <= i)
    {
        if (check(v1, j, i) == 0)
        {
            res = max(res, i - j + 1);
            break;
        }
        else
            j++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

//找得到重复的数返回1
int check(vector& v1, int l, int r)
{
for (int i = l + 1; i <= r; i++)
for (int j = l; j < i; j++)
{
if (v1[i] == v1[j])
return 1;
}
return 0;
}
双指针法二（最终版）：
但是上面代码还是超时，为什么呢？因为check函数写的不好，循环太多，直接是暴力计算找重复数字的，显然不好。

所以引出一个新的check方法：对于寻找是否有重复数字，一般用hash，没人用暴力。所以用hash就可以计算。

但是这道题还有一种计算方法：

用一个辅助数组S保存原数组V1每个元素存在的次数，和hash类似。
比如说 V1 = {1,2, 2, 3, 5 }。那 S就是 {0,1,2,1,0,1 }。S[V1[i]]表示的是V1[i]的个数。
此处我们用S数组只保存 j 和 i 指针之间的数的个数。

算法思路： 如果j = 0，i = 5，此时检查S数组元素都是 <=1的。那下一步的情况就是 i 。i之后将S数组更新，只需要检查S[v1[i]]元素是不是比1大即可，因为随着 i 的递增，S数组中变化的只有S[v1[i]]元素。
如果检查S[v1[i]]元素发现该元素比 1 大。那说明 j 指针和 i 指针之间有某个元素出现了两次。所以 i 指针保持不动， j 指针往后移动( j 指针不可能往前移动的，上次j指针往后移动就是因为 j 和 i之间有重复元素，这一往前移动肯定有重复元素)。j 指针往后移动之前需要先更新S数组，即进行 S[v1[j]]– 操作。然后 j 指针再往后移动。移动之后只需要检查 i 指针对应的S[v1[i]]元素是否大于1即可。（因为 j 指针移动之后只有两种情况，1.重复元素刚好没了，则S[v1[i]]肯定==1；2.重复元素还在，那S[v1[i]]==2，需要 j 继续往后移动 )。等S[v1[i]]==1 时，说明 j 和 i 之间已经没有重复元素了，可以更新res值，然后 i++。

核心代码：

for (int i = 0,j = 0; i < n; i++)
{
    S[v1[i]]++;
    while ( S[v1[i]] > 1) --S[v1[j++]];
    res = max(res, i - j + 1);
}
1
2
3
4
5
6

代码实现：
#include
#include
#include
#define N 100010
using namespace std;

int main()
{
int n;
cin >> n;
vector v1(n,0);
for (int i = 0; i < n; i++)
cin >> v1[i];

vector S(N,0);

int res = 0;
for (int i = 0,j = 0; i < n; i++)
{
    S[v1[i]]++;
    while ( S[v1[i]] > 1) --S[v1[j++]];
    res = max(res, i - j + 1);
}

cout << res;

return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13

}