?LeetCode刷題實戰(zhàn)446：等差數(shù)列劃分 II - 子序列

示例 1：
輸入：nums = [2,4,6,8,10]
輸出：7
解釋：所有的等差子序列為：
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

示例 2：
輸入：nums = [7,7,7,7,7]
輸出：16
解釋：數(shù)組中的任意子序列都是等差子序列。

class?Solution?{
public:
????int?numberOfArithmeticSlices(vector<int>& a)?{
????????typedef?long?long?LL;
????????int?n = a.size();
????????// 表示到i位置為止差值為j的等差序列
????????vector<unordered_mapint>> f(n);
????????int?res = 0;
????????// 枚舉位置
????????for?(int?i = 0; i < n; i ++ )
????????????for?(int?k = 0; k < i; k ++ ) {
????????????????// 枚舉差值
????????????????LL j = (LL)a[i] - a[k];
????????????????auto?it = f[k].find(j);
????????????????int?t = 0;

????????????????// 其中「將 nums[i] 加到以 nums[j] 為尾項，
????????????????// 公差為 d 的弱等差子序列的末尾」這一操作，
????????????????// 實際上就構(gòu)成了一個至少有三個元素的等差子序列，
????????????????// 因此我們將循環(huán)中的 f[j][d] 累加，即為答案。

????????????????// 是否找到k位置之前的差值為j的前一個等差數(shù)列差值
????????????????// 如果找到這樣的等差數(shù)列 證明前面至少有兩個數(shù)
????????????????// 加上現(xiàn)在這個 至少三個數(shù)
????????????????// map的value表示的是以nums[j] 為結(jié)尾、差為map的key且數(shù)組長度為2的等差子序列數(shù)量，
????????????????// 當(dāng)發(fā)現(xiàn)nums[i]-nums[j]等于前面的key，就可以把nums[i]加入進去剛好變成長度為3的等差子序列，而這個數(shù)量也就是map的value。
????????????????// 在遍歷過程中將所有滿足條件的value相加即可
????????????????if?(it != f[k].end()) {
????????????????????// t為f[k][j]的值 表示有多少個等差數(shù)列
????????????????????t = it->second;
????????????????????// 加入答案
????????????????????res += t;
????????????????}
????????????????// 從0到i-1的累加
????????????????f[i][j] = f[i][j] + t + 1;
????????????}
????????return?res;
????}
};