枚舉中間

對于三個或者四個變量的問題，枚舉中間的變量往往更好算。
為什么？比如問題有三個下標，需要滿足 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;}
};