双指针算法

主要思想：

帮助优化双循环算法，原本算法为O(n^2)：

1
2
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)

可以将算法优化为O(n)，此时双指针就像弹簧一样，i在前面扯着j往前移动，然后check它们中间那一段是否合格：

1
2
for (int i = 0, j = 0; i < n; ++i)
    while (j < i && check(i, j)) j++;

基础题

给一个字符串，单词用空格隔开，输出每个单词

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
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string input;
    getline(cin, input);
    for (int i = 0; input[i]; i++)
    {
        // mark the space as the end of the word
        int j = i;
        while (j < input.size() && input[j] != ' ')
            j++;

        for (int k = i; k < j; ++k)
            cout << input[k];
        cout << endl;

        i = j;
    }

    return 0;
}

最长连续不重复子序列

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

输入：

1
2
5
1 2 2 3 5

输出：3 (2, 3, 5)

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
#include <iostream>

using namespace std;
const int N = 100000;
int q[N], s[N];

int main()
{
    int n;
    int result = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &q[i]);

    for (int i = 0, j = 0; i < n; ++i)
    {
        s[q[i]]++;
        while (s[q[i]] > 1)
        {
            s[q[j]]--;
            j++;
        }
        result = max(result, i - j + 1);
    }

    printf("%d", result);
}