codetop标签双指针题目大全解析(C++解法)，双指针刷穿地心！！！

不二刷三刷就是没刷过!!不二刷三刷就是没刷过!!不二刷三刷就是没刷过!!重要的事情说三遍!!!

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

之前学习双指针的总结在这里，传送门->双指针总结

在传送门里有一个题是无重复数字的最长子串
是差不多的，简单哒，没事哒

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char, int> a;//map来记录s某个字符出现多少次int j = 0;//双指针维护的数组是[j，i]int r = 0;//r是最大长度，不断更新for(int i = 0; i < s.size(); i ++){//i是维护数组的右边界a[s[i]] ++;//记录每个s[i]出现的次数while(a[s[i]] > 1){//一旦重复出现了，那么重复的一定是s[i],因为[j， i-1]是维护好了的-- a[s[j ++]];//一遍让j往前推，一遍减掉不在维护数组[j，i]内的字符次数}r = max(r, i - j + 1);}return r;}
};

2.三数之和

还是上一题传送门，里面有原题讲解，这里再贴一遍代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> res;for(int i = 0; i < nums.size(); i ++){if(i && nums[i] == nums[i - 1]) continue;for(int j = i + 1, k = nums.size() - 1; j < k; j ++){if(j > i + 1 && nums[j] == nums[j - 1]) continue;while(j < k && nums[i] + nums[j] + nums[k] > 0) k --;if(j < k && nums[i] + nums[j] + nums[k] == 0) res.push_back({nums[i], nums[j], nums[k]});}}return res;}
};

3.环形链表

很意外的没有一次通过，这一题在传送门里面也有，纯原题
主要是while(fast!=NULL && fast->next != NULL && fast->next->next != NULL)
一开始写成了while(fast!=NULL && fast->next->next != NULL)
不可以跳过fast->next直接判断fast->next->next，如果fast->next == NULL
会触发未定义错误

class Solution {
public:bool hasCycle(ListNode *head) {if(head == NULL || head->next == NULL) return false;ListNode* slow = head;ListNode* fast = head->next;while(fast!=NULL && fast->next != NULL && fast->next->next != NULL){if(slow == fast) return true;fast = fast->next->next;slow = slow->next;}return false;}
};

4.合并两个有序数组

两个非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

要求合并到nums1数组内，需要考虑两个边界，oldIndex和p2，如果p2为空了，剩下的nums1根本不用动，可以直接返回，所以这里while语句里面应该是p2>=0！
这里稍微debug了一会，还是得先想清楚再敲

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int oldIndex = m - 1; // 最后一个有效元素的位置int newIndex = m + n - 1; // 合并后最后一个位置int p2 = n - 1; // nums2的最后一个元素的位置while (p2 >= 0) {if (oldIndex >= 0 && nums1[oldIndex] > nums2[p2]) {nums1[newIndex--] = nums1[oldIndex--];} else {nums1[newIndex--] = nums2[p2--];}}}
};

5.接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

找凹槽，在单调栈的一篇文秒杀整个题型里面也有这个题->传送门

class Solution {
public:int trap(vector<int>& height) {stack<int> s;vector<int> res;int sum = 0;for(int i = 0; i < height.size(); i ++){while(!s.empty() && height[s.top()] < height[i]){int mid = height[s.top()];s.pop();if(!s.empty()){int h = min(height[s.top()], height[i]) - mid;int w = i - s.top() - 1;sum += h * w;}}s.push(i);}return sum;}
};

6.环形链表II

秒杀系列里面的原题
没有秒杀，耻辱的忘记怎么做了，罚自己手写思路

class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head == NULL || head->next == NULL) return NULL;ListNode* slow = head;ListNode* fast = head;while(fast!=NULL&& fast->next!=NULL&&fast->next->next!=NULL){slow = slow->next;fast = fast->next->next;if(slow == fast){ListNode* p2 = slow;ListNode* p1 = head;while(p1 != p2){p1 = p1->next;p2 = p2->next;}return p1;}}return NULL;}
};

7.删除链表的倒数第N个节点

还是双指针传送门的原题，秒了
但是有个地方当时写题解其实没有太明白

1. dummy的必要性，为了同一删除操作，假如链表长度是n，又要删除倒数第n个节点即头结点，加了dummy就不需要单独讨论了
2. 为什么i<=n，注意最后的while(fast)这个地方，当fast来到了表尾，还是能进入循环的，fast再走一步是空，slow还能再走，这样正好可以删除，所以必须slow和fast中间空出两个元素！

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* slow = dummy;ListNode* fast = dummy;for(int i = 0; i <= n; i ++){fast = fast->next;}while(fast){fast = fast->next;slow = slow->next;}ListNode* p = slow->next;slow->next = slow->next->next;delete p;ListNode* newHead = dummy->next;delete dummy;return newHead;}
};

8.训练计划II

这题时间复杂度卡的很松

class Solution {
public:ListNode* trainingPlan(ListNode* head, int cnt) {if(!head) return NULL;int len = 1;//记录链表长度.ListNode *p = head;while(p->next){len++;p = p->next;}p = head;while(len - cnt){p = p->next;len --;}return p;}
};

9.最小覆盖子串

很意外，为什么出现在双指针的标签下
这题考的滑动窗口
紧急写了篇滑动窗口的秒杀文章->传送门
二刷有个容易没注意到的地方：
缩小窗口的时候必须先判断valid–
再window–

class Solution {
public:string minWindow(string s, string t) {unordered_map<char, int> window;unordered_map<char, int> need;for(char c : t) need[c]++;int start = 0;int len = INT_MAX;int left = 0;int right = 0;int valid = 0;while(right < s.size()){char c = s[right];right++;if(need.count(c)){window[c]++;if(window[c] == need[c]) valid++;}while(valid == need.size()){if(right - left < len){start = left;len = right - left;}char a = s[left];left++;if(need.count(a)){if(window[a] == need[a]) valid--;window[a]--;}}}return len == INT_MAX ? "" : s.substr(start, len);}
};

10.回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表。如果是，返回 true ；否则，返回 false 。

力扣234.
思路不难，但是好多细节需要注意
首先不能用双指针总结找中间的节点的办法，因为那个主要是保证fast能走到底，并且slow是会走到双数链表的中间节点靠右第二个
而这题主要是找中点，并且应该是靠左那个
所以直接->next->next就好，这样的fast不一定走到底，但是也不用管了
找到中点之后，将slow后面的指针指向翻转
最后从两边走到中间去比较
用while(p2)判断是否走完，因为p2指的是更短那根，可以把奇数链表中间多余节点忽略掉

class Solution {
public:bool isPalindrome(ListNode* head) {//找中点ListNode* slow = head;ListNode* fast = head;while(fast != NULL && fast->next != NULL && fast->next->next !=NULL){fast = fast->next->next;slow = slow->next;}//slow在的位置就是中点，奇数的话就是中间的数，偶数的话就是中间两个左边的数//反转中点右边的链表ListNode* pre = NULL;ListNode* cur = slow->next;while(cur){ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}slow->next = NULL;//比较两部分链表，第一条从head开始，第二条从pre开始，这个时候的cur已经是空了//从两边开始避免了奇数中间那个多余数的比较//要么一样长，要么第二条短，所以while(p2)ListNode* p1 = head;ListNode* p2 = pre;while(p2){if(p2->val != p1->val) return false;p2 = p2->next;p1 = p1->next;}return true;}
};

11.长度最小的子数组

考滑动窗口的
要注意是大于等于不是等于
看错题目一顿调

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

12.移动零

非0元素前移，这和秒杀双指针里面的移除特定元素是一样的
最后别忘了填充

class Solution {
public:void moveZeroes(vector<int>& nums) {//非0前移int slow = 0;for(int fast = 0; fast < nums.size(); fast ++){if(nums[fast] != 0){nums[slow] = nums[fast];slow++;}}//剩下部分填充0for(; slow < nums.size(); slow ++) nums[slow] = 0;}
};

13.盛水最多的容器

双指针秒杀里面的原题

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

14.旋转链表

整体思路是，将链表头尾连起来，再在新的表尾处砍断
里面有非常多的小细节，比如 k = k % length;
寻找新的表尾：成环右移k个，说明链表倒数第k个会变成表头，for (int i = 0; i < length - k - 1; i++)可以定位到表头前面一个也就是表尾

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (!head || !head->next || k == 0) return head;// 第一步：计算链表长度并形成环形链表ListNode* lastNode = head;int length = 1;while (lastNode->next) {lastNode = lastNode->next;length++;}lastNode->next = head; // 形成环形链表// 第二步：计算实际需要移动的步数k = k % length;if (k == 0) {lastNode->next = NULL; // 恢复链表return head;}// 第三步：找到新的头节点和尾节点ListNode* newTail = head;for (int i = 0; i < length - k - 1; i++) {newTail = newTail->next;}ListNode* newHead = newTail->next;// 断开链表newTail->next = NULL;return newHead;}
};

15.最接近的三数之和

别人写的代码怎么这么优雅┭┮﹏┭┮
重点在于判断最近的，用abs绝对值
if(abs(target - close) < abs(target - closeNum)) closeNum = close
close是当前的三个元素，closeNum是最接近的，初始化为nums[0] + nums[1] + nums[2]

这个return的是和，重复不重复只是降低复杂度，不会改变答案，不用像三数之和一样死扣不重复

class Solution {
public:int threeSumClosest(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int closeNum = nums[0] + nums[1] + nums[2];for(int i = 0; i < nums.size(); i ++){if(i && nums[i] == nums[i - 1]) continue;int left = i + 1, right = nums.size() - 1;while(left < right){int close = nums[i] + nums[left] + nums[right];if(abs(target - close) < abs(target - closeNum)) closeNum = close;if(close > target) right--;else if(close < target) left++;else return target;}}return closeNum;}
};

16.删除有序数组中的重复项

快慢指针，一开始没能灵活应用，还得练

class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 0, fast = 1;while(fast < nums.size()){if(nums[slow] == nums[fast]){fast++;}else{slow++;nums[slow] = nums[fast];}}return slow + 1;}
};

17. 返回倒数第k个节点的值

假如链表长度是k，返回倒数第k个的情况要留意处理
这题题目给的k一定是合理的！

class Solution {
public:int kthToLast(ListNode* head, int k) {ListNode* slow = head;ListNode* fast = head;// fast 指针先前进 k 步for (int i = 0; i < k; i++) {fast = fast->next;}// 同时前进 slow 和 fast，直到 fast 到达链表末尾while (fast != nullptr) {fast = fast->next;slow = slow->next;}// 此时 slow 所指向的即为倒数第 k 个节点return slow->val;}
};

18. 四数之和

双指针秒杀原题

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(), nums.end());vector<vector<int>> res;for(int i = 0; i < nums.size(); i ++){if(i && nums[i] == nums[i - 1]) continue;for(int j = i + 1; j < nums.size(); j ++){if(j > i + 1 && nums[j] == nums[j - 1]) continue;for(int k = j + 1, u = nums.size() - 1; k < u; k ++){//双指针if(k > j + 1 && nums[k] == nums[k - 1]) continue;           while(k < u && (long long)nums[i] + nums[j] + nums[k] + nums[u] > target) u--;if(k < u && (long long)nums[i] + nums[j] + nums[k] + nums[u] == target) res.push_back({nums[i], nums[j], nums[k], nums[u]});}}}return res;}
};

19.验证回文串

先把所有字符转化成小写，并过滤掉空格和标点这类字符。然后对剩下的字符执行双指针中的两端向中心的双指针算法即可。

新学到的库函数：

1. isalnum( c )：isalnum 检查字符c是不是字母或者数字，如果是的话，返回true，不是的话返回false
2. tolower( c )：tolower 将字符 c 转换为小写字母。如果 c 本身是小写字母或非字母字符，返回值将与 c 相同。

class Solution {
public:bool isPalindrome(string s) {string sb;for(int i = 0; i < s.size(); i ++){char c = s[i];if(isalnum(c)){sb += tolower(c);}}//双指针两头往中间验证s = sb;int left = 0, right = sb.size() - 1;while(left < right){if(sb[left] != sb[right]) return false;left++;right--;}return true;}
};

20.字符串的排列

在滑动窗口总结文章里面讲解过了
秒啦

class Solution {
public:bool checkInclusion(string s1, string s2) {unordered_map<char, int> window, need;for(char c : s1) need[c] ++;int left = 0, right = 0;int valid = 0;while(right < s2.size()){char c = s2[right];right++;if(need.count(c)){window[c]++;if(need[c] == window[c]) valid++;}while(right - left > s1.size()){char d = s2[left];left ++;if(need.count(d)){if(need[d] == window[d]) valid--;window[d]--;}}if(need.size() == valid && right - left == s1.size()){return true;}}return false;}
};

21.找出字符串中第一个匹配的下标

拿到手的第一想法就是，滑动窗口，输出left
但是这个要求顺序完全一样，不能是排列或者组合
查了一下KMP是专门弄这种的，学习新算法了(我只是来做双指针的…)这篇文章是个纯刷题记录，不贴详细讲解，最多记录大致思路，需要讲解去秒杀直接部分->传送门

class Solution {
public:int strStr(string haystack, string needle) {int n = haystack.size();int m = needle.size();vector<int> ne(m, -1);// 建next数组for(int i = 1, j = -1; i < m; i ++){while(j != -1 && needle[i] != needle[j + 1]) j = ne[j];if(needle[i] == needle[j + 1]) j ++;ne[i] = j;}// 匹配for(int i = 0, j = -1; i < n; i ++){while(j != -1 && haystack[i] != needle[j + 1]) j = ne[j];if(haystack[i] == needle[j + 1]) j ++;if(j == m - 1){return i - m + 1;}}return -1;}
};

22.最大连续1的个数II

不是，家人们，滑动窗口为什么都划到双指针标签下了啊
题：
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
eg：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
在秒杀系列的滑动窗口秒杀文章里面写过
用滑动窗口做题需要先明白3个问题

1. 什么时候扩大窗口？更改什么数据？
2. 什么时候缩小窗口？更改什么数据？
3. 什么时候得到答案？

针对123的答案：

1. 当可替换次数k>=0的时候扩大窗口，更改窗口里面1的个数，让窗口里面都是1，等于0的时候也扩，万一窗口外面不需要改呢。
2. 当可替换次数k<0的时候缩小窗口，可替换次数++，以便继续扩大
3. k>=0的时候，窗口内部都是1，len更新

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0, right = 0;int windowOneCount = 0;int res = 0;while(right < nums.size()){//right是0也++,是1就windowOneCount++,自身也++if(nums[right] == 1){windowOneCount ++;}right ++;//窗口里面0的个数超过了k,就开始缩小窗口while(right - left - windowOneCount > k){if(nums[left] == 1) windowOneCount --;left ++;}res = max(res, right - left);}return res;}
};

23.数组中的山脉

先找到可能得山顶，再双指针两边扩展，记录res
留意l，r，i的边界

class Solution {
public:int longestMountain(vector<int>& arr) {int l = 0, r = 0, res = 0;for(int i = 1; i < arr.size() - 1; i ++){if(arr[i] > arr[i - 1] && arr[i] > arr[i + 1]){l = i - 1;r = i + 1;while(l > 0 && arr[l] > arr[l - 1]) l --;while(r < arr.size() - 1 && arr[r] > arr[r + 1]) r ++;res = max(res, r - l + 1);}}return res;}
};

24.移除元素

移除val，返回新数组的长度
双指针里也有这题，秒啦

class Solution {public int removeElement(int[] nums, int val) {int i = 0;for (int n : nums)if (n != val) {nums[i] = n;i++;}return i;}
}

25.两个数组的交集II

给nums1和nums2，以数组的形式返回两数组里都存在的数，并且这个数的次数要等于两个数组中这个数出现次数更少的那个

别人的代码是真的优雅
这个代码先记录了nums1中每个元素出现的次数到umap中
再在nums2中for每个元素
如果元素在umap中有记录则将其push进res，并且umap记录数–

假如nums1中才是数字出现少的那个，那么umap[nums1]会先到0，以至于res不了nums2的元素，假如nums2才是数字出现少的那个，那么if(nums2)会先空

太优雅了o(╥﹏╥)o

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {unordered_map<int, int> umap;vector<int> res;for(int i = 0; i < nums1.size(); i ++) umap[nums1[i]]++;for(int i = 0; i < nums2.size(); i ++){if(umap[nums2[i]]){res.push_back(nums2[i]);umap[nums2[i]] --;}}return res;}
};

26.有序数组的平方

给一个非递减的数组，现在需要你将每个元素都平方，然后递增排序，返回nums。注意，需要时间复杂度是O(n)

sort的家伙，以后面试也排人后面！！！！

sort的复杂度是O(nlogn)，所以不能用sort，只能用双指针

这里有个十分关键的点，就是：原本的数组本身就是有序的，是一个非递减的数组，那么即使数组中元素有正有负，绝对值最大的元素肯定是在数组的两端的，即数组平方的最大值是在数组的两端的。

所以我们可以使用两个双指针i,j一个指向起始位置，一个指向数组的末尾。
定义一个新的数组result用于储存新的有序平方后的元素。

class Solution {
public://双指针vector<int> sortedSquares(vector<int>& A) {int k = A.size() - 1; //指向新数组的末尾，从后往前赋值vector<int> result(A.size(), 0);for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素if (A[i] * A[i] < A[j] * A[j]) { //判断条件1：尾部元素更大result[k--] = A[j] * A[j];j--;}else {result[k--] = A[i] * A[i]; //判断条件2：头部元素更大i++;}}return result;}
};

27.删除有序数组中的重复项II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

前2个肯定不用删，所以可以跳过，从j = 2开始比
还是太优雅了这代码

class Solution {
public:int removeDuplicates(vector<int>& nums) {if(nums.size() <= 2) return nums.size();int i = 2;for(int j = 2; j < nums.size(); j ++){if(nums[j] != nums[i - 2]){nums[i] = nums[j];i ++;}}return i;}
};

28.寻找重复数

不可以用sort也不可以用额外数组
这个要求真的是把我路都堵死了…

数组小技巧：数组也可以看做链表来做

class Solution {
public:int findDuplicate(vector<int>& nums) {int fast = 0, slow = 0;while(true){fast = nums[nums[fast]];slow = nums[slow];if(fast == slow) break;}slow = 0;while(fast != slow){fast = nums[fast];slow = nums[slow];}return slow;}
};

29 .水果成篮

fruits数组，fruits[i]代表一种水果，比如fruits[2] = 1，,代表香蕉
现在有fruits.size()棵水果树，每次只能摘一颗树
现在有2个篮子，每个篮子装一种水果，问最多能摘多少棵数

fruit = [1,2,1]，有两种水果树，所以能摘三棵，都能摘，篮子装得下

滑动窗口。要注意不需要window.size() == need，也要计算len，因为有while(window.size() > need)在，窗口不是小了就是刚刚好，不可能大，如果fruit的水果树种类本来就不足2个，就可以返回
另外，当缩小窗口，导致其中一个苹果树没了，window应该erase掉。否则还占用一个size

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int, int> window;int need = 2;int len = 0;int left = 0, right = 0;while(right < fruits.size()){int c = fruits[right];right++;window[c]++;;while(window.size() > need){int d = fruits[left];left++;window[d]--;if(window[d] == 0) window.erase(d);}len = max(len, right - left);}return len;}
};

30.和为k的子数组

给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的子数组个数。子数组是数组中元素的连续非空序列

被骗啦，滑窗酷酷一顿做，结果nums可以有负数
也就是说left++的话窗口和也不一定变小，right++也不一定窗口和变大
滑动窗口失效的时候要用前缀和，前缀和我也写过秒杀系列->传送门

前缀和与子数组的关系是prefix[j] - prefix[i - 1] = k，假设现在遍历到k
先将前缀和prefix[j]存入哈希表，在求prefix[j] - k，看他在不在哈希表，如果在的话，说明存在一个prefix[i - 1]使prefix[j] - prefix[i - 1] = k

1. 将当前累加和减去整数k的结果，在哈希表中查找是否存在
2. 如果存在该key，证明以数组某一点为起点到当前位置满足题意，res+=val
3. 判断当前累加和是否在哈希表中，若存在value+1，不存在则value=1

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int ,int> preSumCount = {{0, 1}};int preSum = 0, count = 0;for(int num : nums){preSum += num;count += preSumCount[preSum - k];preSumCount[preSum]++;}return count;}
};

31.统计[优美子数组]

看起来又很像滑动窗口，但其实最好别用，因为滑动窗口一般用来解决的是窗口符合某个特定条件的问题，而不是窗口的数量，这种情况一般用哈希表和前缀和，并且这题和30其实很像

我们可以通过记录前缀和出现的次数，来计算有多少个符合条件的子数组
prefix_count[i] = k 表示前缀和有i个奇数的数组有k个

class Solution {
public:int numberOfSubarrays(vector<int>& nums, int k) {unordered_map<int, int> preSumNums = {{0, 1}};int count = 0, curSum = 0;for(int num : nums){curSum += (num % 2 == 1 ? 1 : 0);//奇数当1,偶数当0if(preSumNums.find(curSum - k) != preSumNums.end()) count += preSumNums[curSum - k];preSumNums[curSum]++;}return count;}
};

32.区间列表的交集

i为first的行，j为second的行

class Solution {
public:vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {int i = 0, j = 0, n = firstList.size(), m = secondList.size();vector<vector<int>> res;while(i < n && j < m){int l = max(firstList[i][0], secondList[j][0]);int r = min(firstList[i][1], secondList[j][1]);if(l <= r) res.push_back({l, r});firstList[i][1] > secondList[j][1] ? j ++ : i ++;}return res;}
};

33.将x减到0的最小操作

有些题目真的就是破烂(艹皿艹 )
这题考滑动窗口，但是考的很隐蔽，题目说只能移除nums最左边和最右边的元素，目标值是x，可以反着来，目标区间是中间的区域，目标值是sum - x
注意，元素一加立刻right++的话，窗口长度是right-left
for的话因为right会晚一步+1，所以窗口长度是right-left+1

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0, temp = 0, res = -1;for(int num : nums) sum += num;int target = sum - x;if(target < 0) return -1;int left = 0, right = 0;while(right < nums.size()){temp += nums[right];right ++;while(temp > target) temp -= nums[left++];if(temp == target) res = max(res, right - left);}return res == -1 ? -1 : nums.size() - res;}
};

34.替换子串得到平衡字符串

还是滑动窗口，不太一样的是，要观察的是窗口外的元素，可以叫他反向滑动(名字我瞎取得。
设m = n/4。
滑动窗口内部是待替换字符串，窗口外是不替换的。
所以窗口外Q,W,E,R的个数都小于等于m，替换窗口内的字母才可能让字符串平衡。
所以right++意味着外面的元素少一个，这个是替换window需要记录的
如果窗口外有字符大于m，说明窗口内无论怎么替换都无法平衡。
用哈希表统计原串的字符个数
固定左边界，移动右边界。
如果剩余部分不替换的字符串中所有字母个数均≤m，则说明可以构造平衡字符串，则用滑窗长度更新最小替换子串长度
然后移动左边界，对子串长度进行缩小。

class Solution {
public:int balancedString(string s) {int n = s.size();int res = INT_MAX;unordered_map<char, int> a;for(char c : s) a[c] ++;int m = n / 4;if(a['Q'] == m && a['W'] == m && a['E'] == m && a['R'] == m) return 0;int l = 0, r = 0;while(r < n){char d = s[r];r ++;a[d] --;while(a['Q'] <= m && a['W'] <= m && a['E'] <= m && a['R'] <= m){res = min(res, r - l);char c = s[l];a[c] ++;l ++;}}return res;}
};

35.划分字母区间

再强调一遍，不二刷三刷的题目就是没刷过

class Solution {
public:vector<int> partitionLabels(string s) {// 更新每个字母出现的最远下标// 区间内更新其中每个字母出现的最远下标，i等于这个下标的时候片段+1int hash[27] = {0};//hash数组里面是不同字母对应的ascll码的最远下标 for(int i = 0; i < s.size(); i ++){hash[s[i] - 'a'] = i;}vector<int> result;int left = 0;int right = 0;for(int i = 0; i < s.size(); i ++){right = max(right, hash[s[i] - 'a']);if(i == right){result.push_back(right - left + 1);left = i + 1;}}return result;}
};

36.分隔链表

双指针总结里面原题

class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode* dummy1 = new  ListNode(0);ListNode* p1 = dummy1;ListNode* dummy2 = new ListNode(0);ListNode* p2 = dummy2;ListNode* cur = head;while(cur){if(cur->val < x){p1->next = cur;p1 = p1->next;}else{p2->next = cur;p2 = p2->next;}ListNode* temp = cur;cur = cur->next;temp->next = NULL;}p1->next = dummy2->next;delete dummy2;return dummy1->next;}
};

持续更新ing
2024/8/5