同向双指针合集（力扣）

283. 移动零

代码

class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size();int l = 0, r = 0;while(r < n){if(nums[r]){swap(nums[l],nums[r]);l++;}r++;}}
};

209. 长度最小的子数组

代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {   int n = nums.size();int ans = n + 1;int sum = 0;int left = 0, right = 0;for(right = 0; right < n; right++){sum += nums[right];while(sum - nums[left] >= target){sum -= nums[left];left++;}if(sum >= target) ans = min(ans, right - left + 1);}if(ans == n + 1) return 0;return ans;}
};

乘积小于 K 的子数组

代码

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {int n = nums.size();if(k <= 1) return 0;//严格小于1的只有0和负整数，不成立int ans = 0, sum = 1, left = 0, right = 0;for(right = 0; right < n; right++){sum *= nums[right];while(sum >= k){sum /= nums[left];left++;}ans += right - left + 1;}return ans;}
};

3. 无重复字符的最长子串

代码

class Solution {
public:
//空格 常见字符最小的ascii码int cnt[330];int lengthOfLongestSubstring(string s) {int maxnum = 0, l = 0;for(int r = 0; r < s.size(); r++){if(cnt[s[r] - ' '] > 0){while(cnt[s[r] - ' '] > 0){cnt[s[l] - ' ']--;l++;}}maxnum = max(maxnum, r - l + 1);cnt[s[r] - ' ']++;}return maxnum;}
};

438. 找到字符串中所有字母异位词

代码

class Solution {
public:vector<int> findAnagrams(string s, string p) {int n = p.size();map<char,int>mp;for(auto i : p)mp[i]++;int left = 0;vector<int>ans;n = s.size();for(int right = 0 ; right < n; right++){mp[s[right]]--;while(mp[s[right]] < 0){mp[s[left]]++;left++;}if(right - left + 1 == p.size())ans.push_back(left);//因为子串是连续的，且上面处理了非子串的字符必定无法包含进去}return ans;}
};

76. 最小覆盖子串

代码

class Solution {
public:string minWindow(string s, string t) {map<char,int>cnt;int num = 0;for(auto i : t){if(!cnt[i]) num++;//记录字符串里不同字符的种类数cnt[i]++;}int count = 0, l = 0;string tp ="";int minnum = 100010;for(int r = 0; r < s.size();r++){cnt[s[r]]--;if(cnt[s[r]] == 0) count++;//记录已匹配的字符数if(count == num){while(cnt[s[l]] < 0){cnt[s[l]]++;l++;}if(r - l + 1 < minnum){minnum = r - l + 1;tp = s.substr(l,minnum);}cnt[s[l]]++;count--;l++;}}return tp;}
};

---

同向双指针，除了因题目而进行的一些条件的特判外，往往是

1. l r 从起点出发，移动右指针r
2. 移动的过程中根据题目条件对左指针进行移动，从而使得特殊情况也满足条件
3. 根据题目要求的结果，对需要输出的最大长度/子串/起始点进行判断，因为特殊情况也提前被我们处理为了满足条件的情况，所以往往单独放在for循环体的最后进行统计即可。