当前位置：首页 > news >正文

【烧脑算法】三指针的降维打击：三线并行锁定解题细节

news 2025/6/13 18:49:39

引言

三指针

2367. 等差三元组的数目

2563. 统计公平数对的数目

795. 区间子数组个数

2444. 统计定界子数组的数目

总结

引言

三指针算法是一种基于双指针思想的扩展算法，通过引入第三个指针来解决更复杂的数组或链表问题，常用于处理需要同时维护多个区间、元素关系或特定条件的场景。其核心思想是通过三个指针的移动，高效地遍历数据结构，减少时间复杂度（通常为 O(n) 或 O(n^2)），避免暴力枚举的低效性。三指针算法相较于双指针更复杂，并且经常与其他算法进行结合，所以这里只简单分析4个三指针算法习题。

PS：本篇博客中的所有题目均来自于灵茶山艾府 - 力扣（LeetCode）分享的题单。

三指针

2367. 等差三元组的数目

题解：方法一：用set对nums中所有数据进行存储，遍历nums看set中是否存在两个数人与当前元素组成等差三元组。

class Solution {
public:int arithmeticTriplets(vector<int>& nums, int diff) {//使用map来存储nums中的所有值，遍历nums看map中是否存在可以组成等差三元组的数unordered_set<int> s;for(auto e:nums) s.insert(e);int ret=0;for(auto e:nums)if(s.count(e-diff)&&s.count(e+diff)) ret++;return ret;}
};

以上算法的时间复杂度是O(N)，但是空间复杂度是O(N)，能否对空间复杂度进行优化；因为数组是有序的，所以应该往双指针算法上思考。

依旧需要对nums中的数据进行枚举，设枚举到nums[i]： nums[i]-diff，nums[i]，nums[i]+diff三个数据，当nums[i]在向前的时候nums[i]-diff和nums[i]+diff都是在向前的，所以可以使用两个指针来维护nums[i]-diff和nums[i]+diff。

class Solution {
public:int arithmeticTriplets(vector<int>& nums, int diff) {int n=nums.size();int left=0,right=2,ret=0;for(int i=0;i<n&&right<n;i++){//进行左右两边的查找while(nums[left]<nums[i]-diff) left++;while(right<n&&nums[right]<nums[i]+diff) right++;if(right<n&&nums[left]==nums[i]-diff&&nums[right]==nums[i]+diff) ret++;}return ret;}
};

2563. 统计公平数对的数目

题解：由题意得lower-nums[j]<=nums[i]<=upper-nums[j]，当nums[i]在增大的时候，lower-nums[j]和upper-nums[j]都是在减小的，所以可以使用三指针；遍历数组，找到第一个不满足nums[left]>=lower-nums[i]的位置以及第一个满足nums[right]<=upper-nums[i]的位置，此时的(left,right]区间都是有效区间，但是在遍历数组的时候必定会出现重复数据，可以将结果/2。

class Solution {
public:long long countFairPairs(vector<int>& nums, int lower, int upper) {//lower-nums[j]<=nums[i]<=upper-nums[j]//当nums[i]在增大的时候，lower-nums[j]和upper-nums[j]都是在减小的sort(nums.begin(),nums.end());int n=nums.size();int left=n-1,right=n-1;long long ret=0;for(int i=0;i<n;i++){while(left>=0&&nums[left]>=lower-nums[i]) left--; //直到nums[left]<lower-nums[i]即nums[i]<lower-nums[left]while(right>=0&&nums[right]>upper-nums[i]) right--;  //直到nums[right]<=upper-nums[i]//此时的(leftright]是满足条件的if(left<right&&i>left&&i<=right) ret+=right-left-1; //对于i在区间内，i不可取else if(left<right) ret+=right-left;}return ret/2;}
};

对于ret的增加，也可以只取i前面的个数，这样就可以防止结果/2了。

只取i位置前面的个数，就要取min(right+1,i)-min(left+1,i) ；此次要将right+1因为当right==i的时候i是不能取的。

//此时的[left+1,right+1)是满足条件的
ret+=min(right+1,i)-min(left+1,i);

795. 区间子数组个数

题解：如上图所示，以(i0,i1]中任意一个数为左端点，i为右端点都可以组成有效区间。所以关键是找i0和i1，i0就是i前面区间中最后一个大于right的位置，i1就是i前面区间中最后一个>=left&&<=right的位置，i0和i1都是跟着i在向前面进行更新的，所以可以使用三指针进行处理。

总结：在找一个含有某数的区间范围的时候，找到最后一个不满足区间的位置和最后一个满足区间的位置就可以找到能组成有效区间的范围。

class Solution {
public:int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {//遍历数组，找最后一个>right的值，以及最后一个>=left&&<=right的值int n=nums.size(),l=-1,r=-1;int ret=0;for(int i=0;i<n;i++){if(nums[i]>=left&&nums[i]<=right) r=i;if(nums[i]>right) l=i;if(r>l) ret+=r-l;}return ret;}
};

2444. 统计定界子数组的数目

题解：从特殊到一般，与上一题思路一样，以一个位置为终点，在查找左端点；细节：子数组的最大值和最小值与minK和maxK一样，所以在找子数组的时候要注意起始位置的变化。

class Solution {
public:long long countSubarrays(vector<int>& nums, int minK, int maxK) {//使用两个数据来对时候存在相同的最大值和最小值进行标记int n=nums.size();int mini=-1,maxi=-1;long long begin=-1,ret=0;for(int i=0;i<n;i++){if(nums[i]==minK) mini=i;  //修改最近一次的最小值if(nums[i]==maxK) maxi=i;  //修改最近一次的最大值if(nums[i]<minK||nums[i]>maxK) begin=i;  //对起始位置进行修改if(begin<min(mini,maxi)) ret+=min(mini,maxi) - begin;  //更新答案}            return ret;}
};