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;
}和这道题类似的：
83. 删除排序链表中的重复元素
27. 移除元素
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;
}参考资料
- 算法基础课 - AcWing