双指针算法
概念详解
双指针算法（Two Pointers）是用两个下标（指针）在序列上”协作移动”来解决问题的技巧，常见形态有两种：
- 情况一：两个指针分别指向两个序列。 例如归并排序中合并两个有序数组、在两个有序数组中寻找满足条件的数对。
- 情况二：两个指针指向同一个序列的不同位置。 又分两种：① 同向双指针（快慢指针），两个指针都从左往右移动，如找最长不重复子串、数组去重；② 相向双指针，两个指针从两端向中间移动，如有序数组的两数之和、判断回文。
核心思想
因此可知双指针的核心思想就是通过某种性质可以将n^2的复杂度优化为n的复杂度。
为什么能从 O(n²) 降到 O(n)？ 关键点在于：指针 j 不会回退，它和 i 一样，在整个过程中最多各移动 n 次。虽然外层 i 循环了 n 轮、内层还有一个 while，但 while 里的
j++在 n 轮循环中总共最多执行 n 次（j 只增不减），所以总移动次数是 O(n + n) = O(n)，而不是 O(n²)。暴力双循环之所以是 O(n²)，是因为每轮 i 都要让 j 从头扫一遍。使用前提： 判断条件
check必须满足单调性——当 i 向右移动（区间扩大）时，为了重新满足 check，j 只需要向右移动、绝不需要回退。以”最长不重复子序列”为例，i 右移导致区间里可能出现了重复元素，此时 j 只能通过右移来剔除重复，而不是回退。常见应用场景：最长连续不重复子序列、判断回文、有序数组两数之和、数组去重、归并两个有序数组、求两个数组的交集等。
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc= new Scanner(System.in); String str = sc.nextLine(); char[] c = str.toCharArray(); int n = str.length(); for (int i = 0; i < str.length(); i++) { int j = i; while (j < n && c[j] !=' ' ) j++; for (int k = i; k < j; k++) { System.out.print(c[k]); } System.out.println(); i = j; } }}例题
给定一个长度为 n 的整数序列，请找出最长的不包含重复数字的连续子序列，输出它的长度。
输入格式： 第一行包含整数 n。 第二行包含 n 个整数（均在 0~100000 范围内），表示整数序列。
输出格式： 共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。
数据范围： 1 ≤ n ≤ 100000
import java.util.*;
public class Main {
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n= sc.nextInt(); int[] a = new int[n]; int[] b = new int[100010]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } int j =0; int res= 0; for (int i = 0; i < n; i++) { b[a[i]]++; while (b[a[i]] > 1) { b[a[j]]--; j++; } res = Math.max(res,i - j + 1 ); } System.out.println(res); }
}位运算
位运算就是直接在二进制位上做运算。计算机内部所有整数都以二进制补码存储，因此位运算通常比加减乘除更快，也是很多”状态压缩”技巧的基础。
常用位运算符：
| 运算符 | 名称 | 规则 | 示例 |
|---|---|---|---|
& | 按位与 | 两位都为 1 才为 1 | 1010 & 1100 = 1000 |
| | 按位或 | 任意一位为 1 即为 1 | 1010 | 1100 = 1110 |
^ | 按位异或 | 相同为 0，不同为 1 | 1010 ^ 1100 = 0110 |
~ | 按位取反 | 0 变 1，1 变 0 | ~1010 = ...0101（按补码） |
<< | 左移 | 整体左移，低位补 0，相当于乘 2 | 1010 << 1 = 10100 |
>> | 右移 | 整体右移，高位补符号位，相当于除 2 | 1010 >> 1 = 0101 |
补码与负数： 正数的补码就是它的原码；负数 -x 的补码等于 ~x + 1（按位取反再加 1）。例如 x = 10 的二进制（8 位）是 00001010，则 -10 表示为 11110110。补码的好处是减法可以统一成加法来做，这也是下面 lowbit 公式 x & -x 成立的基础。
取出二进制第 k 位：n >> k & 1。 先把 n 右移 k 位，让第 k 位落到最低位，再与 1 做按位与，屏蔽掉其他所有位，结果就是第 k 位的值（0 或 1）。按位与 1 等价于”只看最低位”，这是最常用的取位写法。
其他常用技巧：
- 判断奇偶：
x & 1为 1 则是奇数，为 0 则是偶数（只看最低位）。 - 判断 2 的幂： 若
x > 0且x & (x - 1) == 0，则 x 是 2 的幂（2 的幂的二进制只有一个 1）。 - 交换两个整数：
a ^= b; b ^= a; a ^= b;（利用异或的自反性，无需临时变量）。 - 状态压缩： 用二进制的每一位表示一个集合元素”取/不取”，如
1 << i表示选中第 i 位。
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc= new Scanner(System.in); int n = 2; //把2的二进制每一位打印出来 for (int i = 3; i >= 0; i--) { System.out.print(n >> i & 1); } }}lowbit的实现
lowbit(x) = x & -x，作用是取出 x 的二进制表示中最低位的那个 1 及其右边所有的 0 所构成的数。例如 lowbit(1010) = 10（二进制 10，即十进制的 2）。
原理推导： 由补码知识可知 -x = ~x + 1，因此 x & -x 等价于 x & (~x + 1)。观察 ~x + 1 这个数：以 x 最低位的 1 为分界线——
- 这个 1 右边的位在 x 中是 0，取反后变 1，再加 1 后连续进位，全部变回 0；
- 这个 1 本身，取反变 0、再加 1 又变回 1，所在位不变；
- 这个 1 左边的位取反后与 x 正好相反。
于是 x & (~x + 1) 的结果中，最低位 1 左边的位全被”与”成 0，右边本来就是 0，只剩下最低位的 1 保留下来。这就是 lowbit 只留下”最右边的 1”的原因。
经典应用——统计二进制中 1 的个数： 每次用 n -= lowbit(n) 把最低位的 1 消掉并计数，直到 n 变为 0。每消一次就少一个 1，循环次数恰好等于 1 的个数，效率远高于逐位判断。
public class Main {
public static void main(String[] args) { //cpp中lowbit的实现 int n = 10;//二进制原码为1010 //lowbit的作用是求最右边的1的位置，例如lowbit(1010)结果就是10这是二进制数，对应十进制的2 //lowbit的实现原理就是x&-x //因为-x等同于~x+1,因此可换为x&(~x+1),~x+1中距离最右边的1的右边的数因为取反+1全部变成0,而左右边的1所处位的数不变仍然是1,1左边的数不变仍然是x对应位的取反 //因此最右边的1的左边再计算之后全部为0 int m = n & -n; for (int i = 3; i >= 0 ; i--) { System.out.print(m >> i & 1); } }}import java.util.Scanner;public class Main { public static void main(String[] args) { //输入一个数计算其二进制中1的位数 Scanner sc= new Scanner(System.in); int n = sc.nextInt(); int res = 0; while (n > 0) { n -= lowbit(n); res++; } System.out.println(res); } public static int lowbit(int x){ return x & -x; }}总结
- 双指针的精髓在于利用”指针只前进、不回退”的单调性，把 O(n²) 的暴力枚举优化成 O(n)。写题时先想清楚两个指针各自代表什么、移动条件是什么、check 是否满足单调性。
- 位运算是处理二进制问题的利器：
n >> k & 1取第 k 位、x & -x求 lowbit、x & (x-1)消去最低位的 1、1 << i做状态压缩，这些套路在树状数组、状压 DP 中还会反复出现。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时