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

1.字符串的排列

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

二刷debug：首先，缩小窗口的条件是r-l >s1.size()。然后，必须用need.count( c )而不是need[c] >= 1。count( c ) 仅仅检查键 c 是否存在于 unordered_map 中，与键对应的值无关！而need[c]>=1是必须need中有其键并且数量大于等于1

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

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

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

class Solution {
public:int strStr(string haystack, string needle) {int n = haystack.size();int m = needle.size();vector<int> ne(m, -1);// ne数组必须初始化为-1而不是0,只有-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;}
};

3.最大连续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;}
};

4.数组中的山脉

先找到可能得山顶，再双指针两边扩展，记录res
留意l，r，i的边界
二刷debug：注意双指针两边扩展的手法，还有边界问题，如果是只能到倒数第二个元素的话，i<.size()-1即可

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

5.移除元素

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

6.两个数组的交集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;}
};

7.有序数组的平方

给一个非递减的数组，现在需要你将每个元素都平方，然后递增排序，返回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;}
};

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

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

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

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

二刷debug：不会，很难理解

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

9.寻找重复数

不可以用sort也不可以用额外数组
这个要求真的是把我路都堵死了…
二刷debug：不会…
数组小技巧：数组也可以看做链表来做
以图为例，天然就有数组链表0->1->3->2->4
fast = nums[nums[fast]]相当于fast = fast->next->next
slow = nums[slow]相当于slow = slow->next

几刷？：容易写成return nums[slow]，实际上最后一个是slow = nums[slow]，所以直接写成return slow就可以了

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

10.水果成篮

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

二刷debug：小于等于2的水果树种类也可以，另外unordered_map类型可以使用erase

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