446. 等差數列劃分 II - 子序列

給你一個整數數組?nums?，返回?nums?中所有?等差子序列?的數目。

如果一個序列中?至少有三個元素?，并且任意兩個相鄰元素之差相同，則稱該序列為等差序列。

• 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7]?和?[3, -1, -5, -9]?都是等差序列。
• 再例如，[1, 1, 2, 5, 7]?不是等差序列。

數組中的子序列是從數組中刪除一些元素（也可能不刪除）得到的一個序列。

• 例如，[2,5,10]?是?[1,2,1,2,4,1,5,10]?的一個子序列。

題目數據保證答案是一個?32-bit?整數。

思路：

首先，本道題要求的是所有可能的子序列的數目，要注意此時子序列可以重復出現，因為是友不同位置的同一元素構成的，比如：{5，5，10，15}，可以構成兩個子序列{5，10，15}，{5，10，15}，不同點在于用的5來自不同下標。

再者，對于所求的數量與前面所求數量有所關聯的題，往往會出現dp[i]=dp[j]+1，這里的加一是指會額外多出一種可能，dp[j]表示在原本所有j位置構成的字串加上i位置仍是字串，因此數量不變。

對于本題，由于在找前面符合條件的字串時，涉及到了前面字串的具體構成（因為構成字串最少需要三個元素），因此需要用多維數組表示。dp[i][j]表示i位置數據在前，j位置數據在后，在加上i之前的元素構成子序列，符合條件的數值是2*num[i]-num[j]（因為是等差數列）。然后，由于可以出現重復的子序列，因此對于i位置之前所有符合數值的下標都需要進行加上。

class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {int n=nums.size();vector<vector<int>>dp(n,vector<int>(n));unordered_map<long long,vector<int>>hash;int sum=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){  long long a=(long long)2*nums[i]-nums[j];if(hash.count(a)){for(auto k:hash[a])if(k<i){dp[i][j]+=dp[k][i]+1;}}sum+=dp[i][j];}hash[nums[i]].push_back(i);}return sum;}
};