专题: 双指针题目总结

作者 Lucyyang 日期 2020-03-17
专题: 双指针题目总结

“以大多数人的努力程度之低,根本轮不到拼天赋。”

双指针包含的内容比较杂,我主要将其分为快慢指针(在链表一章中介绍),2sum问题,滑动窗口,二分法(将在二分专题中进行介绍)。

接雨水问题

Trapping Rain Water

首先来一道经典的高频面试题热身。

题目:LC41给定一个数组,里面的数代表强的高度,求最多能装的雨水高度。

接雨水

方法1:这题最关键的突破口是先观察单个点,例如上图中[1,0,1]中间点height[5]能装2个面积的水。这是因为从这点往左边看去,最高的高度是2;往右边看去,最高的高度是3,而它本身高度为0,所以该点可装(min(2,3)-0)。推广结论,对于任意一位置i,其高度应该为min(max(左边高度),max(右边高度))-height[i]。那么最直接的方法就是暴力求解,时间复杂度是O(n^2)。

代码:

class Solution {
public:
int trap(vector<int>& height) {
int N = height.size();
if(N == 0) return 0;
vector<int> left(N), right(N);
left[0] = height[0];
right[N-1] = height.back();
for(int i = 1; i < N; i++){
left[i] = max(left[i-1], height[i]); // for nums[i+1]
}
for(int i = N-2; i>=0; i--){
right[i] = max(right[i+1], height[i]);
}
int ans = 0;
for(int i = 0; i < N; i++) {
ans += min(left[i], right[i]) - height[i];
}
return ans;
}
};

以上代码稍微优化了下,时间复杂度是O(N),空间复杂度是O(N),不过一共要经过三遍遍历。

方法2:接下来采用双指针,将空间复杂度降到O(1)。在这个问题中,我对于每个位置,实际上最关心的是左右最高值中最小的那个,加入我们知道左边的最高值比右边的小,其实我们并不需要具体的右边的数值,我们只会用到左边的最大值。同理如果是右边的最大值比左边的最大值小,那我们需要知道的只是右边的最大值。假设我们有左右两个指针,那么这道题的trick就是,当我们发现位置i的最大值中较小的那个在左边时,我们就求解左边的情况,并进行更新;最大值中右边的较小时,我们求解右边的值,并更新。

int trap(vector<int>& height) {
if (height.empty()) return 0;
int n = height.size();
int left = 0, right = n - 1;
int ans = 0;
int l_max = height[0];
int r_max = height[n - 1];
while (left <= right) {
l_max = max(l_max, height[left]);
r_max = max(r_max, height[right]);
// ans += min(l_max, r_max) - height[i]
if (l_max < r_max) {
ans += l_max - height[left];
left++;
} else {
ans += r_max - height[right];
right--;
}
}
return ans;
}

Container With Most Water

题目:LC11,再来练习一道简单的变种题,这次求的是挑出两个墙之间能存储的最多的水量。

方法:还是可以用双指针实现时间复杂度O(n),空间复杂度O(1)的做法。方法是左右指针分别从两头开始,任意两个墙之间的存水量为(right-left)*min(height[left],height[right])。然后比较左右两堵墙,为了找到更大的值,我们应该更新较小的那个。

代码:

class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size()-1;
int ans = 0;
while(left < right){
ans = max(ans, (right-left)*min(height[left],height[right]));
if(height[left] < height[right])
left++;
else right--;
}
return ans;
}
};

two sum问题

注意在two sum问题中,双指针的方法要应用于有序数组。

three sum

题目:LC15,直接来看two sum的变体,在一个数组中,找到所有三个数相加为0的情况,不考虑数值重复的情况。

方法:先对数组排序,接着遍历i用于第一重循环,left和right用于求解位置i之后的值。如果三个数之和相加小于0,则left++,大于0则right--。

注意:由于数组中含有重复的数,进行判断时需要当前的i是否和i-1的值相同。此外还有跳过left和right各自有重复值的情况。

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
if(nums.size()<=2) return ans;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() -2; i++){
if(i == 0 ||(i>0&&nums[i] != nums[i-1])){
int left = i+1;
int right = nums.size()-1;
while(left<right){
int tmp = nums[left] + nums[right] + nums[i];
if(tmp == 0){
ans.push_back({nums[i], nums[left], nums[right]});
while(left<right && nums[left] == nums[left+1]) left++;
while(left<right && nums[right] == nums[right-1]) right--;
left++;
right--;
}else if(tmp > 0){
right--;
}else {
left++;
}
}
}
}
return ans;
}
};

3Sum Smaller

题目:LC259,3sum的变种,要求只要小于target即可。

方法:依然采用双指针,但只有三个数之和大于等于target时,right--,小于时直接左右求差。

代码:

class Solution {
public:
int threeSumSmaller(vector<int>& nums, int target) {
set<vector<int>> ans_t;
int ans = 0;
if(nums.size() <= 2) return 0;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size()-2; i++){
int left = i+1;
int right = nums.size()-1;
int sum = 0;
while(left < right){
int tmp = nums[i]+nums[left]+nums[right];
if(tmp >= target) {
right--;
}else{
ans += right - left;
left++;
}
}
}
return ans;
}
};

对于有序数组问题双指针方法比较简单,主要是搞清楚,合适移动左右指针。

滑动窗口问题

Minimum Window Substring

题目:LC76,求覆盖给定字符串最小的子串。

方法:滑动窗口的典型问题。left,right指针同时从位置0出发,[left, right]表示一个滑动窗口。right先逐步右移,当能够覆盖的给定子串的时候,left也向右移动,相当于删除单个字符减小区间求最小区间。当不满足给定子串时left停止移动,重新回到right移动的情况。滑动窗口的关键问题在于想清楚right和left什么时候移动什么时候停止。

代码:注意有很多小的细节:

class Solution {
public:
string minWindow(string s, string t) {
int start = 0;
int min_len = INT_MAX;
unordered_map<char, int> windows;
unordered_map<char, int> needs;
for(auto c:t) {
needs[c]++;
}
int left = 0;
int right = 0;
int match = 0;
while(right < s.size()) {
char c1 = s[right];
if(needs.count(c1)) {
windows[c1]++;
if(windows[c1] == needs[c1]) //可能有重复个
match++;
}
right++;
while(match == needs.size()){
char c2 = s[left];
if((right-left) < min_len){ //等于号是当只有一个字符的时候进入
min_len = right-left;
start = left;
}
if(needs.count(c2)){
windows[c2]--;
if(windows[c2] < needs[c2])
match--;
}
left++;
}
}
return min_len == INT_MAX ?
"" : s.substr(start, min_len);
}
};

Minimum Size Subarray Sum

题目:LC209,给定s,在一段非负数组上找到一段最短的连续子序列大于等于s。

方法:典型的滑动窗口做法,两个指针从0出发,当sum < s 不满足条件时,right一直右移并sum += s[right];当满足条件时,再将left右移,找到最短的序列。注意写法:right和left都从0开始,不满足时right一直加,满足条件时先更新最小值。

代码:

class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int left = 0, right = 0;
int ans = INT_MAX;
int sum = 0;
while(right < nums.size()){
sum += nums[right];
right++;
// printf("right=%d\n",right);
while(sum >= s){
ans = min(ans, right - left);//注意right已经++了
sum -= nums[left];
left++;
// printf("left=%d\n",left);
}
}
return ans == INT_MAX? 0:ans;
}
};