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

【烧脑算法】枚举：有序穷举，分步排查

news 2025/7/10 9:27:33

前言

本文是继上一篇【入门算法】枚举：有序穷举，分步排查-CSDN博客，本文将对枚举技巧进行更深一步的分析，将会解析一些难题中如何使用枚举技巧，在一些面试题中枚举的可能不再是变量，也有可能是一段区间。总而言之就是将多变量转化为单变量。

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

枚举进阶题目剖析

1031. 两个非重叠子数组的最大和

题解：枚举右，维护左。此题的特殊之处在于枚举的不再是单个数据，而是一段数组的总和。

class Solution {
public:int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {int n=nums.size();auto all_max=[&](int first,int second){int left=0,right=0;for(int i=0;i<first;i++) left+=nums[i];   //求开始时长度为firstLen的和for(int i=first;i-first<second;i++) right+=nums[i];   //求开始时长度为secondLen的和int ret=left+right,tmp=left;        //tmp来存储左边区间依次向右移动后的区间和结果for(int i=first+second;i<n;i++)     {right+=nums[i]-nums[i-second];   //枚举右tmp+=nums[i-second]-nums[i-second-first];left=max(left,tmp);ret=max(ret,left+right);}return ret;};//两个区间没有前后之分,所以多需要求一遍return max(all_max(firstLen,secondLen),all_max(secondLen,firstLen));  }
};

2555. 两个线段获得的最多奖品

题解：枚举有，维护左。与上题一样此题枚举和维护的都是一段区间，并且两端区间都是滑动窗口。具体方法见下面题解。

class Solution {
public:int maximizeWin(vector<int>& nums, int k) {int n=nums.size();//控制两个区间,保持区间内的最大差控制在k以内int i=0;for(i=1;i<n;i++) if(nums[i]-nums[0]>k) break;   //先找到前面的第一个区间//此时[0,i)是一个区间int l1=0,r1=i-1,l2=i;       //[l1,r1][l2,i]分别表示两个区间int tmp=r1-l1+1,ret=0;for(i=l2+1;i<n;i++)         //枚举右边的区间,维护左边区间的最大值{while(nums[i]-nums[l2]>k){l2++,r1++;while(nums[r1]-nums[l1]>k) l1++;tmp=max(tmp,r1-l1+1);}ret=max(ret,tmp+i-l2+1);}if(l2==n-1) ret=max(ret,tmp+1);  //处理当一个区间就能包含n-1个个数,即不会进入for循环的情况else if(l2==n) ret=max(ret,tmp);       //处理一个区间就能包含所有数的情况return ret;}
};

1995. 统计特殊四元组

题解：本题数据量小能直接使用暴力求解，四个循环O(N^4)。那能否进行优化将时间复杂度降低一些？？？

可以使用枚举右，维护做。对等式进行变形：nums[d]-nums[c]=nums[a]+nums[b]，枚举右边所有的nums[d]-nums[c]，统计左边所有的nums[a]+nums[b]即可。根据题意a<b<c<d所以在统计nums[a]+num[b]的时候应该以c看作分界线，主循环枚举c，依次枚举c左侧的数据作为d看左边有没有满足条件的数据，当c向后走时，再对左边数据和进行扩充即可。

class Solution {
public:int countQuadruplets(vector<int>& nums) {//对等式进行变形: nums[d]-nums[c]=nums[a]+nums[b]//枚举右侧的nus[d]-nums[c],将左边所有的nums[a]+nums[b]进行统计int n=nums.size();unordered_map<int,int> m; //存储左边nums[a]+nums[b]的和m[nums[0]+nums[1]]++;int  ret=0;for(int c=2;c<n-1;c++){for(int d=c+1;d<n;d++)  //枚举c右边的数据作为d{int need=nums[d]-nums[c];if(m.count(need)) ret+=m[need];}for(int j=0;j<c;j++)  //将c位置的数据添加到左边的哈希表中m[nums[j]+nums[c]]++;}return ret;}
};

3404. 统计特殊子序列的数目

题解：与前两题类似，枚举右，维护左。先对等式进行变形，将最小的两个字母和最大的两个字符放到两边：对等式进行变形: nums[p]/nums[q]=nums[s]/nums[r]。此题需要特别注意的是边界情况的控制：q - p > 1 ，r - q > 1 且 s - r > 1 。具体细节见下面代码注释。

class Solution {
public:long long numberOfSubsequences(vector<int>& nums) {//对等式进行变形: nums[p]/nums[q]=nums[s]/nums[r]//枚举右侧的nums[s]/nums[r],将左边所有的 nums[p]/nums[q]进行统计int n=nums.size();unordered_map<double,int> m; //存储左边 nums[p]/nums[q]的值for(int i=0;i<3;i++)   //注意需要间隔一个字符存储{for(int j=i+2;j<3;j++)m[(double)nums[i]/nums[j]]++;}long long ret=0;for(int r=4;r<n-2;r++){for(int s=r+2;s<n;s++)  //枚举s右边的数据作为r{double need=(double)nums[s]/nums[r];if(m.count(need)) ret+=m[need];}for(int p=r-1-2;p>=0;p--)   //将以r-1为分母的商添加到哈希表中m[(double)nums[p]/nums[r-1]]++;}return ret;}
};

3267. 统计近似相等数对 II

枚举右，维护左。

枚举右：将该枚举到的数进行至多两次交换，将所有交换的数统计到set中存储，遍历set中的所有数据在左边找看有没有相等的。

细节：30----->03------>3，30通过交换可以变成3，但是3通过交换不能变成30，也就是说如果30.......3，30在3的前面就会导致3向前找时没有找30的情况，所以要先对数组进行一次排序。

具体代码实现，如下。

class Solution {
public:int countPairs(vector<int>& nums) {int n=nums.size();sort(nums.begin(),nums.end());   //先进行排序,防止数小的无法交换为数大的unordered_map<int,int> m;int ret=0;for(int i=0;i<n;i++){unordered_set<int> tmp;   //存储当前数据经过之多两次交换后的值tmp.insert(nums[i]);       //存储数字本身string str=to_string(nums[i]);    //将整数转化为字符串方便交换int len=str.size();  for(int i=0;i<len;i++){for(int j=i+1;j<len;j++) {swap(str[i],str[j]);tmp.insert(stoi(str));   //交换一次for(int p=i+1;p<len;p++){for(int q=i+1;q<len;q++){swap(str[p],str[q]);   //交换两次tmp.insert(stoi(str));swap(str[p],str[q]);    //换回来}}swap(str[i],str[j]);   //换回来}}for(auto x:tmp)ret+=m.count(x)?m[x]:0;   //遍历交换后的数字,在前面找又没有相同的m[nums[i]]++;   //将当前位置加入和左边进行维护}return ret;}
};