双指针

原理

• 两个序列，例题（1）。
• 一个序列：
  • 头尾指针，例题（2）。
  • 头头指针，例题（3）。

代码

// 一个序列 - 头尾指针
for (int i = 1, j = n; i <= n; ++ i) {
    while (j > i && 条件不成立) -- j;
    if (i != j) { // 条件成立
        // ...
    } else { // i 等于 j，此时条件可能成立也可能不成立
        // ...
        break;
    }
}

// 一个序列 - 头头指针
for (int j = 1, i = 1; j <= n; ++ j) { // [i, j]
    // add(j)
    while (i < j && 条件不成立) ++ i;
    // ...
}