每日算法刷题Day35 6.22:leetcode枚举技巧枚举中间2道题，用时1h

枚举中间

对于三个或者四个变量的问题，枚举中间的变量往往更好算。
为什么？比如问题有三个下标，需要满足 0≤i<j<k<n，对比一下：
枚举 i，后续计算中还需保证 j<k。
枚举 j，那么 i 和 k 自动被 j 隔开，互相独立，后续计算中无需关心 i 和 k 的位置关系。
所以枚举中间的变量更简单。

1.套路

class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int n=nums.size();
        // 后缀数组维护k的最小值
        vector<int> sufMin(n,0);
        sufMin[n-1]=nums[n-1];
        for(int i=n-2;i>=0;--i){
            sufMin[i]=min(sufMin[i+1],nums[i]);
        }
        int preMin=nums[0],res=INT_MAX;
        // 枚举j,注意j范围[1,n-1)
        for(int j=1;j+1<n;++j){
            if(nums[j]>preMin && nums[j]>sufMin[j+1])   res=min(res,preMin+nums[j]+sufMin[j+1]);
            // 单变量维护i的最小值
            preMin=min(preMin,nums[j]);
        }
        if(res==INT_MAX)    return -1;
        else    return res;
    }
};

2.题目描述

1.给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件(题目条件)，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]
  请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和(答案) 。如果不存在满足条件的三元组，返回 -1 。
  2.给你一个整数数组 nums。
  特殊三元组 **定义为(题目条件)**满足以下条件的下标三元组 (i, j, k)：
• 0 <= i < j < k < n，其中 n = nums.length
• nums[i] == nums[j] * 2
• nums[k] == nums[j] * 2
  返回数组中 特殊三元组的总数(答案)。
  由于答案可能非常大，请返回结果对 109 + 7 取余数后的值。

3.学习经验

1.i的维护跟枚举右，维护左一样，可以随着j的枚举而动态更新，所以可以用单变量或者map(更新答案后加入j)实现，但k的维护需要在枚举j之前完成，通常要借助数组和map(更新答案前删去j),无法用一个变量实现

1. 2909.元素和最小的山形三元组II(中等，学习,前后缀最小值维护)

2909. 元素和最小的山形三元组 II - 力扣（LeetCode）

思想

1.给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]
  请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。
  2.这题三个变量，所以要枚举中间变量j,而nums[i]的最小值维护可以跟着j的枚举一起更新，所以只需要一个变量preMin即可，但是nums[j+1]-nums[n-1]的最小值无法只用一个变量维护，需要提前递推算出后缀最小值(类似于前缀和),令$sufMin[i]$表示[i,n)的最小值，所以得到递推公式:
  $sufMin[i]=min(sufMin(i+1),nums[i])$,从后向前更新，在枚举j前维护即可
  3.所以满足山形条件为:

nums[j]>preMin && nums[j]>sufMin[j+1]

更新答案:

res=min(res,pre+nums[j]+sufMin[j+1])

更新preMin:

preMin=min(preMin,nums[j])

代码

c++:

class Solution {
public:
    int minimumSum(vector<int>& nums) {
        int n=nums.size();
        // 后缀数组维护k的最小值
        vector<int> sufMin(n,0);
        sufMin[n-1]=nums[n-1];
        for(int i=n-2;i>=0;--i){
            sufMin[i]=min(sufMin[i+1],nums[i]);
        }
        int preMin=nums[0],res=INT_MAX;
        // 枚举j,注意j范围[1,n-1)
        for(int j=1;j+1<n;++j){
            if(nums[j]>preMin && nums[j]>sufMin[j+1])   res=min(res,preMin+nums[j]+sufMin[j+1]);
            // 单变量维护i的最小值
            preMin=min(preMin,nums[j]);
        }
        if(res==INT_MAX)    return -1;
        else    return res;
    }
};

2. 3583.统计特殊三元组(中等)

3583. 统计特殊三元组 - 力扣（LeetCode）

思想

1.给你一个整数数组 nums。
特殊三元组 定义为满足以下条件的下标三元组 (i, j, k)：

• 0 <= i < j < k < n，其中 n = nums.length
• nums[i] == nums[j] * 2
• nums[k] == nums[j] * 2
  返回数组中 特殊三元组 的总数。
  由于答案可能非常大，请返回结果对 109 + 7 取余数后的值。
  2.学习1. 2909.元素和最小的山形三元组II的思想，本题需要知道[0,j-1]中nums[j]*2的个数和[j+1,n)中nums[j]*2的个数，前者就是正常的枚举右，维护左会用到的map技巧，后者也可以利用这个思想，不过我的代码复杂了，还开了一个数组来计算，可以直接用map,再计算答案前先把nums[j]减去即可,而前者是计算答案后要把nums[j]加上,因为枚举j，所以i和k相互独立，用乘法原理相乘即可

代码

c++:
我的代码

class Solution {
public:
    int specialTriplets(vector<int>& nums) {
        const int mod = 1e9 + 7;
        int n = nums.size();
        map<long long, long long> suf;  // 维护k,数-个数
        vector<long long> sufCnt(n, 0); // 维护k，个数
        map<long long, long long> pre;  // 维护i,数-个数
        for (int i = n - 1; i >= 0; --i) {
            sufCnt[i] = suf[2 * nums[i]];
            ++suf[nums[i]];
        }
        long long res = 0;
        ++pre[nums[0]];
        for (int j = 1; j + 1 < n; ++j) {
            res = (res + pre[nums[j] * 2] * sufCnt[j]) % mod;
            ++pre[nums[j]];
        }
        return res;
    }
};

优化:

class Solution {
public:
    int specialTriplets(vector<int>& nums) {
        const int mod = 1e9 + 7;
        int n = nums.size();
        map<long long, long long> suf; // 维护k,数-个数
        map<long long, long long> pre; // 维护i,数-个数
        // 跟下面j的范围一样
        for (int j = 1; j < n; ++j)
            ++suf[nums[j]];
        long long res = 0;
        ++pre[nums[0]];
        for (int j = 1; j + 1 < n; ++j) {
            --suf[nums[j]];
            res = (res + pre[nums[j] * 2] * suf[nums[j] * 2]) % mod;
            ++pre[nums[j]];
        }
        return res;
    }
};