4 - 双指针
准备春招，算法题冲冲冲！
如果某些数据具有单调性，可以尝试使用双指针算法来减少时间复杂度。
双指针
思路
针对问题先想一个暴力的方法（通常是i 和 j 之间有单调关系，则可以利用这种单调关系写一个双指针算法，以减少时间复杂度。
双指针算法的一般写法如下：
for (int i = 0, j = 0; i < n; ++i) { while (j < i && check(i, j)) j++; // 每道题目的具体逻辑... }
时间复杂度为
例题
799. 最长连续不重复子序列
这道题可以用双指针来做，用 i 维护连续不重复子序列的右端，用 j 维护连续不重复子序列的左端。输入 a[i] 后，让 map[a[i]] 计数增加，如果出现重复（map[a[i]] > 1），就让 j 右移，别忘了 map[a[j]] 计数减少。最后剩下的就是连续不重复子序列，长度为 i - j + 1，记录它的最大值就是答案。
#include <iostream> #include <vector> #include <unordered_map> using namespace std; int main() { int n; cin >> n; vector<int> a(100001); unordered_map<int, int> map; int lengthMax = -1; for (int i = 0, j = 0; i < n; ++i) { cin >> a.at(i); map[a.at(i)] += 1; // 看看是否重复了, 重复就右移j while (j <= i && map[a.at(i)] > 1) { map[a.at(j)] -= 1; ++j; } // 记录当前连续区间最长长度 lengthMax = max(lengthMax, i - j + 1); } cout << lengthMax; }
800. 数组元素的目标和
#include <iostream> #include <vector> using namespace std; int main() { int n, m, x; cin >> n >> m >> x; vector<int> a(100001), b(100001); for (int i = 0; i < n; ++i) cin >> a.at(i); for (int i = 0; i < m; ++i) cin >> b.at(i); // 一个从左开始, 一个从右开始 for (int i = 0, j = m - 1; i < n; ++i) { // 如果大于给定和, 就让j往左走 while (j >= 0 && a.at(i) + b.at(j) > x) --j; // 找到唯一解 if (a.at(i) + b.at(j) == x) { cout << i << " " << j; break; } } }
2816. 判断子序列
#include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> a(n), b(m); for (int i = 0; i < n; ++i) cin >> a.at(i); for (int i = 0; i < m; ++i) cin >> b.at(i); // i -> a[], j -> b[] for (int i = 0, j = 0; j < m; ++j) { if (a.at(i) == b.at(j)) { ++i; // i == n说明a数组已被全部遍历完, a是b的子序列 if (i == n) { cout << "Yes"; return 0; } } } cout << "No"; }
53. 最大子数组和
可以用双指针来做，用 i 从头遍历到尾求和，如果和为负，就让 j 往前走，同时让和减去 a [j]。
int maxSubArray(vector<int>& nums) { int maxSum = nums.at(0); int tmpSum = 0; for (int i = 0, j = 0; i < nums.size(); ++i) { tmpSum += nums.at(i); maxSum = max(maxSum, tmpSum); while (tmpSum < 0) { tmpSum -= nums.at(j++); } } return maxSum; }
283. 移动零
用双指针来做，左边的指针永远指向 0，右边的指针永远指向非 0 元素，然后进行交换即可。
void moveZeroes(vector<int>& nums) { int n = nums.size(); for (int left = 0, right = 0; right < n; ++right) { while (left < right && nums.at(left) != 0) { ++left; } if (nums.at(left) == 0 && nums.at(right) != 0) { swap(nums.at(left), nums.at(right)); } } }
11. 盛最多水的容器
用双指针来做，左边的指针在 0，右边的指针在 height.size() - 1。注意到 当移动较短的板时，容器面积可能增大，我们只需一直移动较短的板，直到双指针相遇即可。
int getArea(vector<int>& height, int left, int right) { return min(height.at(left), height.at(right)) * (right - left); } int maxArea(vector<int>& height) { int ans = 0; for (int left = 0, right = height.size() - 1; left < right;) { ans = max(ans, getArea(height, left, right)); while(left < right) { if (height.at(left) < height.at(right)) ans = max(ans, getArea(height, ++left, right)); else ans = max(ans, getArea(height, left, --right)); } } return ans; }
167. 两数之和 II - 输入有序数组
使用双指针，一个在最左边，另一个在最右边，如果两数之和太小，让左指针右移；反之让右指针左移；最终返回答案。
参考代码如下：
vector<int> twoSum(vector<int>& numbers, int target) { int left = 0, right = numbers.size() - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) return {left + 1, right + 1}; else if (sum < target) ++left; else --right; } return {-1, -1}; }
15. 三数之和
遇事不决先排序，排完序后就能用双指针了。
我们让 i 从头到尾遍历一次，j 指向 i 的下一个元素向右移动，k 指向数组的最后一个元素向左移动，然后：
- 如果
num[i] + num[j] + num[k] == 0，就将这三个数添加到答案中； - 如果三数之和大于 0，说明
num[k]太大了，让它左移； - 如果三数之和小于 0，说明
num[j]太小了，让它右移：
此外，答案中有重复元素，需要在添加答案后进行去重操作；此外，还有优化的地方，如果 nums[i] 已经大于 0 了，那三数之和怎么加都大于 0，就没必要继续了。正确的代码如下：
vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; sort(nums.begin(), nums.end()); for (int i = 0, j = 1, k = nums.size() - 1; i < nums.size() - 1; ++i) { j = i + 1, k = nums.size() - 1; // 如果num[i] > 0, 它后面的元素也必大于0 if (nums.at(i) > 0) break; // 跳过重复元素 if (i >= 1 && nums.at(i) == nums.at(i - 1)) continue; // 找j和k while (j < k) { int sum = nums.at(i) + nums.at(j) + nums.at(k); if (sum > 0) --k; else if (sum < 0) ++j; else { ans.push_back({nums.at(i), nums.at(j), nums.at(k)}); --k, ++j; // 跳过重复元素 while (j < k && nums.at(j) == nums.at(j - 1)) ++j; while (j < k && nums.at(k) == nums.at(k + 1)) --k; } } } return ans; }
42. 接雨水
利用双指针和两个变量（记录左 / 右侧最高点）即可 “竖着接雨水”：
- 从两头开始遍历，分别记录左边和右边的最大高度
- 如果现在左边的高度比右边的低，说明左边的最大高度也比右边的低；左边可以进行接水；
- 反之，右边可以进行接水。
- 接完水后不要忘了顺便让双指针位移。
int trap(vector<int>& height) { int ans = 0; int lMax = 0, rMax = 0; int left = 0, right = height.size() - 1; while (left < right) { lMax = max(lMax, height.at(left)); rMax = max(rMax, height.at(right)); if (left < right && height.at(left) < height.at(right)) ans += lMax - height.at(left++); if (left < right && height.at(left) >= height.at(right)) ans += rMax - height.at(right--); } return ans; }
26. 删除有序数组中的重复项
这道题使用双指针，左边的指针遍历到重复数字就停止，右边的则找到下一个不重复的，与左边交换。
代码如下：
int removeDuplicates(vector<int>& nums) { int left = 0; for (int right = 0; right < nums.size(); ++right) { if (nums[left] != nums[right]) { ++left; nums[left] = nums[right]; } } return left + 1; }
和这道题类似的：
5. 最长回文子串
首先，先写一个找回文串的算法：使用双指针，从中心向两端扩散。而对于中心位置的确定分两种情况，如果回文串长度为奇数，那么中心位置就有一个；如果是偶数，中心位置就有两个。因此找回文串的算法可以这样写：
string getPalindrome(const string& s, int left, int right) { while (left >= 0 && right < s.size() && s[left] == s[right]) { left--; right++; } return s.substr(left + 1, right - left - 1); }
接下来看看如何找最长回文子串，我们只需遍历字符串所有位置，分回文串长度为奇偶两次情况获取回文子串，然后取最长即可：
string longestPalindrome(string s) { string ans = ""; for (int i = 0; i < s.size(); ++i) { string s1 = getPalindrome(s, i, i); string s2 = getPalindrome(s, i, i + 1); ans = ans.size() < s1.size() ? s1 : ans; ans = ans.size() < s2.size() ? s2 : ans; } return ans; }