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

1.和为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;}
};

2.统计[优美子数组]

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

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

二刷debug：忘记了

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;}
};

3.区间列表的交集

i为first的行，j为second的行

二刷debug：firstList[i][1] > secondList[j][1] ? j ++ : i ++;想了会，不是很熟

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;}
};

4.将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;}
};

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

二刷debug：忘记了不会

还是滑动窗口，不太一样的是，要观察的是窗口外的元素，可以叫他反向滑动(名字我瞎取的
设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;}
};

6.划分字母区间

返回的是每个小区间的长度
二刷debug：思路有点乱

class Solution {
public:vector<int> partitionLabels(string s) {unordered_map<char, int> map;int right = 0, left = 0;vector<int> res;for(int i = 0; i < s.size(); i ++) map[s[i]] = i;//记录最远坐标for(int i = 0; i < s.size(); i ++){right = max(right, map[s[i]]);if(i == right){res.push_back(right - left + 1);left = right + 1;}}return res;}
};

7.分隔链表

双指针总结里面原题
二刷debug：一次过

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;}
};

8.通过删除字母匹配到字典里最长单词

注意题目说的是返回长度最长且字母序最小的
字母序指的是字母的的ASCLL码值
长度最长是优先级1，字典序最小是优先级2

我A不出来老老实实看题解学习

• 首先排序dictionary，使他符合排序优先级1和优先级2
• 遍历字符串数组dictionary中的字符串，用双指针i和j分别代表检查到s和dictionary[x]中的字符串
• 当s[i] != dictionary[x]，使i指针右移，如果相等的话，i和j都右移
• 当j == p.size()的时候，说明dictionary中有一个字符串匹配完了，由于dictionary已经按照优先级排列了，所以直接输出

细节解释：两个优先级怎么解决？
用lambda函数来定义，该函数决定了两个字符串 a 和 b 的比较方式。

sort(dictionary.begin(), dictionary.end(), [](const string& a, const string& b) {return a.length() > b.length() || (a.length() == b.length() && a < b);});

a.length() > b.length()：首先比较字符串 a 和 b 的长度。如果 a 的长度大于 b 的长度，则返回 true，意味着 a 应该排在 b 前面。这部分使得较长的字符串排在字典向量的前面。
(a.length() == b.length() && a < b)意思是：如果两个字符串长度相等，则比较它们的字典顺序。如果 a 在字典顺序上小于 b，则返回 true，意味着 a 应该排在 b 前面。这保证了长度相同的字符串按字典顺序排序。

二刷debug：边界情况考虑模糊，比如这里最后是 if (j == p.size())，容易写成p.size(）-1
完整代码：

class Solution {
public:string findLongestWord(string s, vector<string>& dictionary) {sort(dictionary.begin(), dictionary.end(), [](const string& a, const string& b) {return a.length() > b.length() || (a.length() == b.length() && a < b);});for (const auto& p : dictionary) {int i = 0, j = 0;while (i < s.size() && j < p.size()) {if (s[i] == p[j]) j++;i++;}if (j == p.size()) return p;}return "";}
};

9.寻找目标值-二维数组

简单点说就是，这个园林树木的高度排列有迹可循，让你找一个高度target

思路：二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。
为什么从右上角找？要是从左上角，目标值只可能等于左上角或者大于左上角，大于的话你都不知道往哪里走，只有右上角才有唯一路走

如果plants.empty()为true，说明二维数组是空的，那么plants[0].size()就会因为非法访问报错

二刷debug:

1. plants.size是行，plants[0].size()是列
2. 判断plants和target关系的时候只能用if，用while的话i，j会超
3. 判空，为空的话plants[0].size()就会因为非法访问报错

class Solution {
public:bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {if(plants.empty()) return false;int i = plants.size() - 1, j = 0;while(j >= 0 && j < plants[0].size() && i >= 0 && i < plants.size()){if(plants[i][j] < target) j ++;else if(plants[i][j] > target) i --;else return true;}return false;}
};

10.至多包含两个不同字符的最长子串

会员题

显然用滑动窗口

class Solution {
public:int lengthOfLongestSubstringTwoDistinct(string s) {int valid = 0;unordered_map<char, int> window;int ans = 1;int left = 0;int right = 0;while (right < s.length()) {char c = s[right];if (window[c] == 0) {valid++;}window[c]++;// 窗口缩小，左指针右移while (valid > 2) {char deleteChar = s[left];left++;window[deleteChar]--;if (window[deleteChar] == 0) {valid--;}}ans = max(ans, right - left + 1);right++;}return ans;}
};

11.最小差

给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差
有用例[-2147483648,1]，[2147483647,0]
必须用long，因为：

-2147483648 是 int 类型的最小值。 2147483647 是 int 类型的最大值。

如果选择 a 中的 -2147483648 和 b 中的 2147483647 进行计算，差值为：

2147483647 - (-2147483648) = 2147483647 + 2147483648 = 4294967295

这个结果 4294967295 超出了 int 类型的表示范围（int 的范围是 -2147483648 到 2147483647）。所以必须用long

class Solution {
public:int smallestDifference(vector<int>& a, vector<int>& b) {sort(a.begin(), a.end());sort(b.begin(), b.end());long dist = INT_MAX;int i = 0, j = 0;while(i < a.size() && j < b.size()){long temp = a[i] - b[j];dist = min(dist, abs(temp));if(temp < 0) i ++;else j ++;}return dist;}
};