C++双指针法（尺取法）原理及模板代码与例题

双指针法（尺取法）

双指针法，又名 尺取法（Sliding Window/Two Pointers） ，能够解决区间问题；例如，找出和不小于 k 的最小连续区间。 双指针的运作方式，类似用尺蠖虫一曲一伸的爬行方式。尺蠖虫在日文中写作尺取虫，尺取法可能源自于此。 尺取法是一种高效的区间处理技巧，常用于解决连续子区间/子数组/子字符串问题。其核心是通过两个指针（左、右边界）动态调整窗口范围，结合条件判断快速找到满足要求的区间，时间复杂度通常为 O(n)。

---

核心原理 窗口定义：用 left 和 right 指针表示窗口的左右边界。窗口扩展：right 指针向右移动，尝试扩大窗口，直到满足条件。窗口收缩：一旦窗口满足条件，left 指针向右移动，尝试缩小窗口，寻找更优解或统计结果。终止条件：right 指针遍历完整个数组/字符串。

---

应用场景 最小覆盖子串最长无重复子串和为特定值的连续子数组固定长度的子数组最大值统计满足条件的区间数量

---

通用模板代码 void slidingWindow(string s, string t) { unordered_map<char, int> need, window; // 统计字符需求及当前窗口 for (char c : t) need[c]++; // 初始化需求 int left = 0, right = 0; // 窗口边界 int valid = 0; // 记录窗口中满足需求的字符数量 while (right < s.size()) { // 1. 扩大窗口：移动 right 指针 char c = s[right++]; if (need.count(c)) { // 如果当前字符是目标字符 window[c]++; if (window[c] == need[c]) valid++; // 满足需求时更新 valid } // 2. 收缩窗口：移动 left 指针（根据条件判断） while (valid == need.size()) { // 当前窗口满足所有需求 // 在这里处理结果（如记录最小长度） // 缩小窗口 char d = s[left++]; if (need.count(d)) { if (window[d] == need[d]) valid--; // 窗口不再满足需求时更新 window[d]--; } } } // 返回最终结果 }

---

典型问题解析 1. 最长无重复字符子串 int lengthOfLongestSubstring(string s) { unordered_map<char, int> window; int left = 0, right = 0; int max_len = 0; while (right < s.size()) { char c = s[right++]; window[c]++; // 收缩窗口：直到重复字符消失 while (window[c] > 1) { char d = s[left++]; window[d]--; } max_len = max(max_len, right - left); } return max_len; } 2. 找到所有字母异位词（固定窗口） vector<int> findAnagrams(string s, string p) { unordered_map<char, int> need, window; for (char c : p) need[c]++; vector<int> res; int left = 0, right = 0, valid = 0; while (right < s.size()) { char c = s[right++]; if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } // 固定窗口大小：当窗口长度等于 p 的长度时收缩 while (right - left >= p.size()) { if (valid == need.size()) res.push_back(left); char d = s[left++]; if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } return res; } 3.连续的正整数段，使得段中所有数之和为 N for (int l = 1, r = 2, sum = 3; l <= n/2;) { if (sum == n) { cout << l << ' ' << r << endl; sum -= l, l++; } else if (sum < n) { r++, sum += r; } else { // sum > n sum -= l, l++; } }

---

关键技巧 数据结构：使用哈希表（如 unordered_map）快速统计字符频率。移动条件： 扩展窗口：当窗口不满足条件时，移动 right。收缩窗口：当窗口满足条件时，移动 left 寻找最优解。 边界处理：注意指针移动时对哈希表的更新顺序（如先检查再增减）。复杂度：由于每个元素最多被 left 和 right 各访问一次，时间复杂度为 O(n)。

---

例题： 题目描述

给定一个正整数 N，请你求出所有的连续的正整数段，使得段中所有数之和为 N， 每段至少有两个数字。

例如：1998+1999+2000+2001+2002=10000，所以从 1998 到 2002 的一个自然数段为 N=10000 的一个解。

用 l 和 r 代表区间的左右端点，sum 记录区间数字和； 当 sum 小于目标值 N 时，将右端点右移，sum会变大； 当 sum 大于目标值 N 时，将左端点右移，sum会变小 ； 如果 sum==N，意味着找到答案，则输出； 因为，双指针都是单调向右移动，也只扫一遍，所以时间复杂度为O(n) ； 左端点大于N/2时即可停止，因为区间长度至少为2，区间和再不会小于 N 了。