双指针算法

核心思路

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

相关例题

快速排序

https://www.acwing.com/problem/content/787/

# include <iostream>

using namespace std;

const int N = 100010;
int n, q[N];

void quick_sort(int q[], int left, int right)
{
    if (left >= right) return;
    int i = left - 1, j = right + 1;
    int x = q[(left + right) / 2];
    while (i < j)
    {
        do i ++; while (q[i] < x);
        do j --; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, left, j);
    quick_sort(q, j+1, right);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> q[i];
    quick_sort(q, 0, n-1);
    for (int i = 0; i < n; i ++) cout << q[i] << ' ';
    return 0;
}

归并排序

https://www.acwing.com/problem/content/789/

主要思想：分治
快速排序：不稳定；归并排序：稳定
1. 确定分界点
2. 递归排序left和right
3. 归并：将两个数组合并为一个有序的序列

# include <iostream>

using namespace std;

const int N = 100010;
int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int mid = (l + r) / 2; // 确定分界点
    merge_sort(q, l, mid), merge_sort(q, mid+1, r); // 递归left和right

    // k：当前tmp内有多少个数：两个序列合并的时候已经合并了几个数
    // i：左半边起点，j：右半边起点
    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];

    for (i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> q[i];
    merge_sort(q, 0, n-1);
    for (int i = 0; i < n; i ++) cout << q[i] << ' ';
}

61. 最长不含重复字符的子字符串

https://www.acwing.com/problem/content/57/

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<char, int> heap;
        // j在前，i在后
        int res = 0;
        for (int i = 0, j = 0; i < s.size(); i ++)
        {
            heap[s[i]] ++; // 每次将当前字母加到哈希表中
            // 当出现重复字符时j往后移动一位
            while (heap[s[i]] > 1) heap[s[j ++]] --;
            res = max(res, i - j + 1);
        }
        return res;
    }
};

799.最长连续不重复子序列

https://www.acwing.com/problem/content/801/

 // s：当前j到i区间内每个数出现的次数
int n, 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 (j <= i && s[a[i]] > 1)
        {
            s[a[j]] --;
            j ++; // j往前移动一位
        }
        res = max(res, i - j + 1);
    }
    cout << res;
}

800.数组目标和

https://www.acwing.com/problem/content/802/

int n, m, x;
int a[N], b[N];

int main()
{
    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;
            break;
        }
    }
}

2816.判断子序列

https://www.acwing.com/problem/content/2818/

int i = 0, j = 0;
while (i < n && j < m)
{
    if (a[i] == b[j]) i ++;
    j ++;
}
if (i == n) puts("Yes");
else puts("No");

合并两个有序的数组

https://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665?tpId=295&tqId=658&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj

void merge(int A[], int m, int B[], int n)
{
    int len = m + n;
    int l1 = m - 1, l2 = n - 1;
    for (int i = len-1; i >= 0; i --)
    {
        if (l1 >= 0 && l2 >= 0)
        {
            if (A[l1] > B[l2])
            {
                A[i] = A[l1];
                l1 --;
            }
            else
            {
                A[i] = B[l2];
                l2 --;
            }
        }
        else if (l2 >= 0)
        {
            A[i] = B[l2];
            l2 --;
        }
    }
}

字符串的调整

https://www.nowcoder.com/practice/c53c017b757d4c02b6666b40bfa49a27?tpId=101&tqId=33183&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3Fdifficulty%3D1%26page%3D1%26pageSize%3D50%26search%3D%26tpId%3D101%26type%3D101&difficulty=1&judgeStatus=undefined&tags=&title=

```
cin >> s;
int n = s.size();
int j = n - 1;
for (int i = n - 1; i >= 0; i –) if (s[i] != ‘’) s[j –] = s[i];
while (j >= 0) s[j –] = ‘’;
cout << s << endl;