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