0. 常用枚举技巧

常与固定长度的滑动窗口或变长滑动窗口（双指针）搭配

0.1 枚举右，维护左（双变量问题）

双变量问题 f(a[i] + a[j]) = C，可以转化为单变量问题 (i < j)：a[j] = f-1(C) – a[i]，即在a[j]的左侧查找是否满足条件的情况，因此在遍历时可以用哈希表维护

例题

1010. 总持续时间可被 60 整除的歌曲 – 力扣（LeetCode）

class Solution {
public:
    /* 
      time[j]%60 = 60 - time[i]%60
      哈希表中存入time[i]%60的值，枚举j查找哈希表中是否有 60 - time[j]%60的值
    */
    int numPairsDivisibleBy60(vector<int>& time) {
        int n = time.size();

        // 存入time[i]%60的值的个数
        unordered_map<int, int> mp;

        // 边存边找
        int ans = 0;

        for(int i = 0; i < n; ++i){
            ans += (mp.find(60 - time[i]%60) != mp.end())?mp[60 - time[i]%60]:0;
            ++mp[(time[i] % 60 == 0)?60:time[i]%60];
        }

        return ans;
    }
};

此处不需要使用真的哈希表，可用数组进行模拟

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int ans = 0, cnt[60]{};

        for(const int& t: time){
            ans += cnt[(60 - t%60)%60];  // 注意 t = 60的情况：其被存入到cnt[0]中
            ++cnt[t%60];
        }
        return ans;
    }
};

练习

基础

进阶

3185. 构成整天的下标对数目 II – 力扣（LeetCode）

2748. 美丽下标对的数目 – 力扣（LeetCode）

注：2748题虽然算简单题，但很有内容，此处单独拉出解决

class Solution {
public:
    // 此题已经告诉了gcd函数的作用，可以直接拿来用
    /*
        The std::gcd function in C++ is used to compute the greatest common divisor (GCD) of two integers. 
        This function is available in the <numeric> header and was introduced in C++17.

        C++17 - <algorithm>  __gcd

        for example:
            gcd(12, 9)  返回 12和9的最大公约数3 
    */ 

    /*
        枚举右，维护左
        转换为判断 第j个元素 (最后一个数字) 的美丽下标对个数, cnt数组记录 左侧第一个元素的 数字个数
    */

    int countBeautifulPairs(vector<int>& nums){
        int ans = 0, cnt[10]{};

        for(int num: nums){
            // 判断第j个元素的美丽下标对个数
            for(int i = 1; i < 10; ++i)
                if(cnt[i] && gcd(i, num % 10) == 1) ans += cnt[i];
            
            // 维护第一个数字个数
            while(num / 10 > 0)
                num /= 10;
            ++cnt[num % 10];
        }

        return ans;
    }
};

Q：此处若限制使用gcd，又该如何快速求解呢？

可以先预处理出互质表

class Solution {
public:
    // 成员变量 - 互质表
    const vector<int> coprime[10] = {
        {},
        {1,2,3,4,5,6,7,8,9},
        {1,3,5,7,9},
        {1,2,4,5,7,8},
        {1,3,5,7,9},
        {1,2,3,4,6,7,8,9},
        {1,5,7},
        {1,2,3,4,5,6,8,9},
        {1,3,5,7,9},
        {1,2,4,5,7,8}
    };


    int countBeautifulPairs(vector<int>& nums){
        // 记录左侧第一个数字的个数
        int hash[10]{};

        int ans = 0;

        for(int num: nums){
            // 取最后一个元素
            int x = num % 10;
            for(int i = 0; i < coprime[x].size(); ++i)
                ans += hash[coprime[x][i]];
            
            // 维护哈希表
            while(num / 10 > 0)
                num /= 10;
            
            ++hash[num];
        }

        return ans;
    }
};

2506. 统计相似字符串对的数目 – 力扣（LeetCode）

由于该题words[i]仅有小写字母组成，有个好的想法：把字符串 s 中出现过的字母视作一个集合，把这个集合压缩成一个二进制数 mask。其中 mask 第 i 位为 1 表示第 i 个小写字母在 s 中，为 0 表示不在。

集合与位运算的知识点参考科学刷题 – 枚举 — 二进制枚举

2874. 有序三元组中的最大值 II – 力扣（LeetCode）

对于三个变量的最值问题：i < j < k ，求max( nums[i] – nums[j] ) * nums[k]，这类题可以枚举k，通过一次遍历即可解决问题（思路十分巧妙）

枚举k，需要维护三个值：

• ans 取决于 k左侧的 nums[i] – nums[j] 的最值 maxdiff
• maxdiff 取决于 prefmax – nums[j] 的最值
• prefmax 取决于 nums[j] 左侧的最值

具体过程如图：

class Solution {
public:
    long long maximumTripletValue(vector<int>& nums){
        int n = nums.size();
        long long ans = 0;
        int maxdiff = 0, prefmax = 0;

        for(const int& x: nums){
            ans = max(ans, 1LL * maxdiff * x);   // 1LL妙用：将int类型转换为了long long 类型
            maxdiff = max(maxdiff, prefmax - x);
            prefmax = max(prefmax, x);
        }
        
        return ans;
    }
};

2874. 有序三元组中的最大值 II – 力扣（LeetCode）

此题有两种思路可以解决问题：

• 不断的去推区间（固定左边界->右边界， 左右边界的最值），然后将左边界置于上一个区间的右边
• 固定长度的滑动窗口 (firstlen + secondlen)，枚举右，记录左侧的最大值（更推荐）

2555. 两个线段获得的最多奖品 – 力扣（LeetCode）【套路】- 推荐时常复习

此题核心思想在于在一次遍历中第二条线段的右端点一定在第一条线段的右端点前面，因此可以枚举第二条线段的右端点的同时统计以每个点为右端点之前的奖品最大数量

1995. 统计特殊四元组 – 力扣（LeetCode）

此题设计四个数之间的关系，a < b < c < d，满足nums[a] + nums[b] + nums[c] = nums[d]

转换为 nums[a] + nums[b] = nums[d] – nums[c] 的问题

阿Q思路如下：

待计算加入哈希表的元素的右侧，即为：待差值计算查找哈希表的元素个数，因此枚举中间变量即可

3404. 统计特殊子序列的数目 – 力扣（LeetCode）

此题和1995题很类似，将 p < q < r < s, nums[p] * nums[r] = nums[q] * nums[s] 转换为连续的情况

nums[p] / nums[q] = nums[s] / nums[r]

此题关键在于：

• 存储分式，可以用最简分式存取， map<pair<int, int>, int> mp
• 双精度和单精度浮点数对应题中数值大小问题：取1附近的两个值 (a – 1)/a，a / (a + 1)，两个值作差 1 / (a * (a + 1))，对于双精度：当差值小于 2 ^ (-52)时，计算机可能会将这两个数赋值到一个浮点数上，此时 a = 2^26，而题中 nums[i] <= 1000，远小于该值。 单精度：差值小于 2 ^ (-23)时，a = 2^(11.5)，因此该题可直接用单精度求解即可

3267. 统计近似相等数对 II – 力扣（LeetCode）

此题思想十分的暴力，传统的维护左，枚举右；难度在于：如何去判断近似相等数对！

思想：枚举出右边界所有的近似相等数对（此处为优化点），再依次去找哈希表中该种数对的数量进行累加

Q：如何枚举出某数的所有近似相等数对呢？有以下几种方案：

• 将数转为字符串，然后交换1/2次，加入到集合中；统计完所有的近似相等数对后遍历集合，查找哈希表中某数对的数量

    for(int right = 1; right < n; ++right){
        int x = nums[right];
        // 集合 - 可能交换有重复的情况出现(暴力枚举)
        unordered_set<int> st = {x};
        
        string s = to_string(x);

        int m = s.size();

        // 此处怎么生成近似相等数对？
        // 交换一个位次（i），然后交换其右侧的任意两个位次
        for(int i = 0; i < m; ++i){
            for(int j = i + 1; j < m; ++j){
                swap(s[i],s[j]);
                st.insert(stoi(s));

                for(int p = i + 1; p < m; ++p){
                    for(int q = p + 1; q < m; ++q){
                        swap(s[p], s[q]);
                        st.insert(stoi(s));
                        // 一定要恢复原形
                        swap(s[p], s[q]);
                    }
                }
                swap(s[i], s[j]);
            }
        }

• 该思想即为重要：用数组存储数，nums[i] = 123，对应数组 N = [3, 2, 1]；设置一个10的幂次数组（由于只有7位，因此用七位数组即可）：pow10 = [1, 10, 100, 1000, 10000, 100000, 1000000]
  好处：N 和 pow10 对应位置相乘累加即为nums[i]
  交换 N[i], N[j]，x增量的数学表达式为：
  ~x = (N[i] – N[j]) * pow10[j] + (N[j] – N[i]) * pow10[i] = (N[i] – N[j]) * (pow10[j] – pow10[i])

for(int right = 1; right < n; ++right){
    int x = nums[right];
    unordered_set<int> s = {x};

    int m = 0;
    for(int k = x; k; k /= 10){
        N[m++] = k % 10;
    }

    // 进行一次遍历
    for(int i = 0; i < m; ++i){
        for(int j = i + 1; j < m; ++j){
            // 一次优化：若N[i], N[j] 相等，则x未有任何变化
            if(N[i] == N[j]) continue;
            // 进行一次交换
            // 将 y = x + 增量存入集合中
            int y = x + (N[i] - N[j]) * pow10[j] + (N[j] - N[i]) * pow10[i];
            s.insert(y);

            // 交换该两个位置
            swap(N[i], N[j]);

            // 进行第二次交换
            for(int p = i + 1; p < m; ++p){
                for(int q = p + 1; q < m; ++q){
                    // 和上述同理
                    if(N[p] == N[q]) continue;
                    s.insert(y + (N[p] - N[q]) * pow10[q] + (N[q] - N[p]) * pow10[p]);
                }
            }

            // 恢复原位
            swap(N[i], N[j]);
        }
    }

• 灵神的更进一步优化十分难想，考虑两个数都进行一次或零次交换而碰到的中间值是否相同，
  meet in the middle + bitset

过程如下：

const int pow10[7] = {1, 10, 100, 1000, 10000, 100000, 1000000};

int countPairs(vector<int>& nums){
    int ans = 0;
    // 使用集合论的思想解决该问题
    int n = nums.size(), N[7];
    unordered_map<int, bitset<5000>> num_to_set;

    int maxnum = ranges::max(nums, {}, {});
    int maxsize = 0;
    for(;maxnum;maxnum /= 10)
        ++maxsize;

    for(int i = 0; i < n; ++i){
        // nums[i] = 123, 转换为数组 N = [3,2,1]
        int x = nums[i];
        
        // 此处必须转换为相同位数才能保证该算法运行正确
        int v = x;
        for(int i = 0; i < maxsize; ++i){
            N[i] = v % 10;
            v = v / 10;
        }

        unordered_set<int> st = {x};

        // 一次交换即可，然后使用集合论解决问题
        for(int p = 0; p < maxsize; ++p){
            for(int q = p + 1; q < maxsize; ++q){
                if(N[p] == N[q]) continue;
                st.insert(x + (N[p] - N[q]) * (pow10[q] - pow10[p]));
            }
        }

        // 使用集合
        bitset<5000> bp, idx = 0;  // 表示当前的元素
        bp.set(i);

        for(const int& v: st){
            // 之前的值经过一次交换得到相同的中间值
            idx |= num_to_set[v];
            num_to_set[v] |= bp;
        }

        ans += idx.count();
    }
    return ans;
}

3480. 删除一个冲突对后最大子数组数目 – 力扣（LeetCode）

若从左到右考虑，则此题难度极大(容易超时)；

换个角度，从右到左，此时对于i，只需要考虑其右边界即可（难度系数骤减）

枚举左侧位置 i， 维护右侧（a >= i）的最小值b0和次小值b1

计算冲突对全部存在的情况ans，此外计算删除b0冲突对的增量，返回最大增量 + ans即为最值

思维扩展