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

前言

本文是继上一篇【入门算法】枚举：有序穷举，分步排查-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;
    }
};

总结

在上面题目中，有各种各样的枚举技巧，有些是3个三个变量的，4个变量的或者是区间的。只要抓住一个关键位置，来对多变量进行简化，转化为单变量的问题即可。