目录
本篇博客是对【入门算法】单序列双指针：从暴力枚举到高效优化的思维跃迁-CSDN博客的补充，主要探讨了更高难度的双指针算法题目。有些题目的双指针的隐藏较深或者代码实现有一定难度，通过对每个leetcode题目的分析帮助读者进一步提升对双指针算法的掌握和应用能力。PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。
相向双指针
1498. 满足条件的子序列数目
题解：通过相向双指针，通过left来找到一个满足right位置，此时left就可以与(left,right]中的任意一个子数组形成满足条件的子数组。计算子数组的数目是可以直接使用2^(right-left)但是可能存在越界，所以此处先进行预处理将nums.size()个2的幂存放起来即解决了越界的问题还能够节约时间。
class Solution {
#define MOD 1000000007
public:
int numSubseq(vector<int>& nums, int target) {
//使用双指针进行处理
//先进行预处理来记录每一个2的幂次方
int n=nums.size();
vector<int> two(n);
two[0]=1;
for(int i=1;i<n;i++) two[i]=2*two[i-1]%MOD;
sort(nums.begin(),nums.end());
int left=0,right=nums.size()-1;
int ret=0;
while(left<=right) //注意：此处可以相等，left一个也可以组成子数组
{
if(nums[left]+nums[right]>target) right--;
else
{
//此时left与(left,right]区间内任意的子数组都可以形成满足条件的子数组
ret=(ret+two[right-left])%MOD;
left++;
}
}
return ret;
}
};1782. 统计点对的数目
题解：要计算两个数的边数之和>querier[i]所以需要统计每个数字存在的边数；将统计结果放入到count数组中-------->此题就转化为了在一个数组中找两个元素其和>queries[i]的个数；但是注意可能出现重复的情况，比如示例1：count[1]+count[2]的个数是3+4但是[1,2]和[2,1]使得计数出现了重复，所以在每一个结果中都要对可能出现的重复情况进行处理，可以将每一个点对存储到map中去，在对结果进行调整时可以采用：遍历map减去map中出现的重复结果，具体来说就是map<pair<int,int>,int> ，pair中存储的点对是1和2，出现的次数是c，那么如果count[1]+count[2]>queries[i]但是count[1]+count[2]-c<=queries就说明该不满足的情况被记录了，将ret[i]-=1即可。
class Solution {
public:
vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
vector<int> count(n+1); //存储每一个数字与多少条边相连
map<pair<int,int>,int> repeat; //记录i<j中每个组合出现的次数
for(auto e:edges)
{
int x=e[0],y=e[1];
if(x>y) swap(x,y); //保证x始终是小于y的，方便map进行计数
count[x]++,count[y]++;
repeat[{x,y}]++;
}
//此时count存储了从1----n中每个数其他数相连的边数
//此题就转化为了在数组count中找两个不同的位置使其之和>queries[i]即可
//但是直接使用count中的数据必定会出现重复数据,比如[1,2]的范围直接将count[1]+count[2]就会多计数
//对于重复数据需要进行处理
//可以使用同向双指针进行实现
vector<int> tmp(count);
sort(tmp.begin(),tmp.end()); //将count进行排序
vector<int> ret(queries.size());
for(int i=0;i<queries.size();i++)
{
int left=1,right=n,num=0;
while(left<right)
{
if(tmp[left]+tmp[right]<=queries[i]) left++;
else
{
ret[i]+=right-left;
right--;
}
}
//对重复数据进行处理
for(auto [pa,num]:repeat)
{
int x=pa.first,y=pa.second;
if(count[x]+count[y]>queries[i]&&count[x]+count[y]-num<=queries[i])
ret[i]--;
}
}
return ret;
}
};581. 最短无序连续子数组
题解：找到一个无序区间，该区间通过排序后可以使得数组有序？？？
可以将数组分为三段：左端有序，右端有序，找到中间段即可；如何找到中间段呢？？？设中间段的最大值为max，中间段的最小值为min，从左向右遍历中间段最后一个小于max的位置就是end，从右向左遍历中间段最后一个大于min的就是begin。
从左向右找end：当nums[i]>max时更新max，否则更新end位置；
从右向左找begin：当nums[i]<min时更新min，否则更新begin位置。
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
//从左向右最后一个小于中间段max的就是右边界
//从右向左最后一个大于中间段min的就是左边界
int n=nums.size();
int max=nums[0],min=nums[n-1];
int end=0,begin=0;
for(int i=0;i<n;i++)
{
if(nums[i]<max) end=i;
else max=nums[i];
if(nums[n-1-i]>min) begin=n-1-i;
else min=nums[n-1-i];
}
if(end<=begin) return 0;
return end-begin+1;
}
};
同向双指针
2122. 还原原数组
题解：根据题意，首先可以确定数组中最小的元素就是lower[0]，但是数组中的heigher[0]无法确定，也就不能确定k的值。无法确定heigher[0]的值，就对数组中的值进行枚举，将nums[i]作为heigher[0]看哪一个合适。细节先对数组进行排序，在进行枚举时，我们要记录哪些位置是heigher数组的元素来防止lower数组进行访问，所以可以使用一个布尔数组记录heigher的元素。
class Solution {
public:
vector<int> recoverArray(vector<int>& nums) {
//lower[i]+k==arr[i]==heigher[i]-k
//将数组进行排序后,lower[0]一定是nums[0],但是heigher[0]不确定,所以可以枚举nums[i]作为heigher[0]
int n=nums.size();
sort(nums.begin(),nums.end());
if(nums[0]==nums[n-1])
return vector<int>(n/2,nums[0]); //如果数组中的值全部相等就可以直接将数组进行返回
for(int i=1;i<=n/2;i++)
{
if((nums[i]-nums[0])%2==1||(nums[i]-nums[0])==0) continue;
vector<bool> vis(n,false); //保存那些值是heigher数组中的
vector<int> ret;
int prev=0,cur=i,k=(nums[i]-nums[0])/2;
while(cur<n)
{
if(nums[cur]-nums[prev]<2*k) cur++;
else if(nums[cur]-nums[prev]>2*k) break; //当出现大于的情况就不可能再有满足条件的值了
else
{
vis[cur]=true; //将该位置记录为heigher数组的，防止lower数组进行访问
ret.push_back(nums[cur]-k);
cur++,prev++;
while(prev<cur&&vis[prev]==true) prev++; //找到lower数组的下一个位置
}
}
if(ret.size()==n/2) return ret;
}
return {};
}
};2972. 统计移除递增子数组的数目 II
题解：此题需要统计满足条件的子数组的个数，将所有可以子数组都枚举出来？？？O(N^2)会出现超时；那应该如何进行优化呢？？？根据题意要形成递增子数组，此处可以采用枚举每个右端点作为最后一个删除的位置，向前找有多少个可以删除的起点将其相加即可。
细节实现：枚举每一个后缀j，将j-1作为删除位置的最后一个元素，在前面找有多少个起始删除位置(即该数值是第一个小于nums[j]的位置)，将所有后缀对应的起始位置进行相加即可。此题同样是同向双指针，先找到前缀的第一个波峰作为i，然后让j=n-1，让j和i都向前移动。注意：此处进行删除时是以j-1作为删除的最后一个位置，但是数组也可以从某个位置开始向后删除完，该位置可以从0....i+1，从这些位置开始删除都是可以的，所以ret一开始应当置为i+2而不是0。
class Solution {
public:
long long incremovableSubarrayCount(vector<int>& nums) {
//先找到前缀的第一个波峰
int i=0,n=nums.size();
while(i<n-1&&nums[i]<nums[i+1]) i++;
if(i==n-1) return (long long)n*(n+1)/2; //如果数组本身就是有序的，删除任意一个子数组都是可以的
long long ret=i+2; //ret是返回的结果，i+2是可以删除后缀的个数，从i位置向后一直删除完的个数
int j=n-1;
while(j==n-1||nums[j]<nums[j+1])
{
while(i>=0&&nums[i]>=nums[j]) i--; //找到第一个小于nums[j]的位置，可以删除[]
ret+=i+2;
j--;
}
return ret;
}
};
思维拓展
1920. 基于排列构建数组
题解：使用O(N)的空间，进行模拟得到所有的答案。
class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
int n=nums.size();
vector<int> ret(n);
for(int i=0;i<n;i++)
ret[i]=nums[nums[i]];
return ret;
}
};拓展：能否使用O(1)的空间得出结果？？？？
根据题目数组的数据都在0~N以内，所以从i开始不断让i=nums[i]一定会让i回到原来的位置，所以可以通过在对i位置的值进行改变之前，先对下标为nums[i]的位置进行改变，直到i回到原来位置后时停止；有点类似于挖坑法，先将i位置数值保留，对i进行挖坑，再用以nums[i]为下标的值将该位置填起来。如何确定一个位置时候被修改呢？？？数组所有元素都是正数，所以可以用负数来对已经修改的位置进行标记，将-(nums[i]+1)即可。
class Solution {
public:
vector<int> buildArray(vector<int>& nums) {
//使用O(1)的时间复杂度实现
int n=nums.size();
for(int i=0;i<n;i++)
{
int x=nums[i];
if(x<0) continue; //如果小于0说明该位置已经被修改了，继续下一个位置
int hole=i; // 当前位置需要被填
int j=nums[i]; //hole的下一个位置下标
while(j!=i)
{
nums[hole]=-(nums[j]+1); //将坑填起来
hole=j; //继续下一个位置
j=nums[hole];
}
nums[hole]=-(x+1); //将回到i位置的前一个位置进行修改
}
for(int i=0;i<n;i++)
nums[i]=-nums[i]-1; //将数组还原
return nums;
}
};442. 数组中重复的数据
题解：题目要求处理结果不能意外，使用常量的额外空间。解法一：直接开nums[i]最大值个空间进行解决；
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int count[100001]={0}; //直接开nums[i]最大值的空间
vector<int> ret;
for(auto e:nums)
{
count[e]++;
if(count[e]==2) ret.push_back(e);
}
return ret;
}
};上面代码只是开个玩笑)))，现在思考一下如何用O(1)进行统计出现了两次的数据？？？根据题意：1<=nums[i]<=n，n==nums.lenth()，这有点像哈希表哩，下标从0~n-1，数据从1-n其之间只相差了1，能否使用nums作为我们的哈希表？？？此处可以，怎么进行计数？题目中nums[i]都是>0的所以可以通过正负来表示计数，负数表示已经出现过一次的数据，整数表示好没有出现的数据，当num[nums[i]-1]是负数时说明重复了。
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
int n=nums.size();
vector<int> ret;
for(int i=0;i<n;i++)
{
int j=abs(nums[i]); //对该位置的数据要取绝对值
if(nums[j-1]<0) ret.push_back(j); //已经存在了
else nums[j-1]=-nums[j-1]; //第一次存在
}
return ret;
}
};448. 找到所有数组中消失的数字
题解：能否在O(N)的时间复杂度下，在仅使用常量空间(返回数组不算)的情况下解决题目，与上一题一样还是使用正负来标记已经出现的数值。
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
//使用nums最为哈希桶来标记每个位置是否出现
int n=nums.size();
for(int i=0;i<n;i++)
{
int j=abs(nums[i]);
if(nums[j-1]>0)
nums[j-1]=-nums[j-1]; //用负数标记存在的数字
}
vector<int> ret;
for(int i=0;i<n;i++)
if(nums[i]>0) ret.push_back(i+1);
return ret;
}
};41. 缺失的第一个正数
题解：要想办法使用nums来标记存在的正数即可；找数组中缺失的第一个正数，该元素一定在1~n+1之间的一个值，所以只需要记录1~n+1之间的数字是否出现即可，可以使用下标来对应存储的值，用下标为i的位置来对应nums[i]-1；可以通过交换将每一个数据换到其对应的下标位置，最后遍历数组第一个下标与数值不对应的位置就是答案。
对于非区间内的数值不需要进行处理，对于数值与下标已经对应的位置不需要进行交换。
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
//有1-n个数据，其正数最大的情况就是1-n中每个数nums中都存在
//将1-n中的每个数都交换到对应的位置，最后遍历数组第一个下标+1与数值不相等的位置就是答案
int n=nums.size();
for(int i=0;i<n;i++)
{
int x=nums[i];
while(x<=n&&x>0&&nums[x-1]!=nums[i]) //不在区间的数值不需要进行交换，数值与下标位置已经对应不进行交换
{
swap(nums[i],nums[x-1]); //将对应数值交换到对应下标位置
x=nums[i]; //看交换来的位置是否还需要进行交换
}
}
for(int i=0;i<n;i++)
if(nums[i]!=i+1) return i+1; //找下标与数值不对应的位置
return n+1;
}
};287. 寻找重复数
此题类似于142. 环形链表 II，如果没有做过该题可以先去试试环形链表这一题。
题解：根据题意n+1个元素，数据范围在[1,n]之间，那么每一个元素都会对应一个下标，重复的元素就会出现一对多的情况；因为一对多使得本题类似与环形链表，通过下标与数值建立起链表的联系，比如示例一：0----->1，1----->3，2---->4，3----->2，4----->2，箭头前面是下标，后面是对应的元素。
此时通过下标与数值之间的映射关系就形成了一个环形链表，此时寻找重复数------>求入环点。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
//用数组模拟链表
//寻找重复数------>寻找入环位置
int n=nums.size();
int slow=0,fast=0;
while(slow==0||slow!=fast)
{
slow=nums[slow];
fast=nums[nums[fast]];
}
//此时是相交位置
int prev=0;
while(prev==0||prev!=slow)
{
prev=nums[prev];
slow=nums[slow];
}
return prev;
}
};