双指针算法

一、核心思想

1
找单调性，优化暴力枚举。找单调性，找单调性，让指针不用回退可以一往无前~
1
2
3
4
5
6
7
8
9
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        O(n^2)
//将上面的暴力算法优化到O(n)  
//核心思想就是观察出暴力思维中的单调关系，优化算法，
for(int i = 0, j = 0; i < n; i++){
    while(j < i && check(i,j)) j++
        //每道题目的具体逻辑
}

二、例题

例题1：输出字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//输入abc def ghi
//输出每个单词，分别占一行
#include <iostream>
#include <string.h>
using namespace std;

int main(){
    char str[1000];
    fgets(str, 100, stdin);//gets()被淘汰了
    
    int n = strlen(str);
    
    for(int i = 0; i < n; i++){
        int j = i;
        while(j < n && str[j] != ' ') j++;//i指向a.j指向空格
        //这道问题的具体逻辑
        for(int k = i; k < j; k++) cout<<str[k];
        cout<<endl;
        
        i = j;//让i指向j也就是空格，再++就能跳过整个区间直接指到下一个单词
    }
    return 0;
}

例题2：最长连续不重复子序列

1
2
3
4
5
6
7
8
9
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。

输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//———————————————————法一：暴力法——————————————————————
//时间复杂度O(n^2)，很容易超时间
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int q[N];
int res, n;

bool check(int l, int r){
    for(int i = l + 1 ; i <= r; i++)
        for(int j = l; j < i; j++)
            if(q[j] == q[i]) return false;
    return true;
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= i; j++)
            if(check(j, i)) res = max(res, i - j + 1);
    cout<<res;        
    return 0;
}
//——————————————————————法二：双指针法——————————————————————
//仍然超时
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int q[N];
int res, n;

bool check(int l, int r){
    for(int j = l; j < r; j++)
        if(q[j] == q[r]) return 1;
    return 0;
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    for(int i = 0; i < n; i++){
        int j;							//发现j只能单调向i移动
        while(j <= i && check(j,i)) j ++;//如果j到i之间有重复元素，j++，
        res = max(res, i - j + 1);        

    }
    cout<<res;        
    return 0;
}
//—————————————————————————————双指针法二————————————————————————————
//通过辅助数组，标记每个数出现的次数，这个思想非常好
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n;
int a[N],S[N];//辅助数组s记录每个数出现的次数


int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    
    int res = 0;
    for(int i = 0, j = 0; i < n; i ++){
        S[a[i]] ++;
        while(S[a[i]] > 1){//当出现重复数的时候，j ++直到重复数被剔除
            S[a[j]] --;
            j++;        //j移动后，j之前所指向的数出现的个数--
        }              //当j移动到i的位置的时候，循环结束
        res = max(res, i - j + 1);
    }
    cout<<res;
    return 0;
}
//——————————————————————————双指针法三————————————————————————————
//用哈希表，待续