动态规划

状态表示：f[i][j]表示以ai结尾的并且公差是j的长度>=2的 等差数列的个数。

状态转移分析：

​ 表面上看，我们要枚举i，再枚举j，最后枚举k。但是我们发现，条件成立的时候j是不需要枚举的，只和i，k有关，则只需要两重循环，且j是公差，范围很大，但是数量很小，我们需要用哈希表来存。

状态表示是>=2长度，如何求>=3的呢？

肯定是枚举每一序列>=3的长度的末尾为a[k]。实际上，我们状态枚举的时候，当枚举到长度>=3的时候，我们累加即可。

什么时候状态>=3呢？

状态转移过程中，我们a[i]接到a[k]后面，若a[k]前面还有序列，则长度>=3，那么这个时候，长度>=3的长度个数就是f[k][j]个。我们将所有的f[k][j]累加起来。

时间复杂度$O(N^2)$，空间复杂度$O(N^2)$

AC代码

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& a) {
        int n = a.size();
        typedef long long LL;
        vector<unordered_map<LL,int>> 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;
                if (it != f[k].end()) {
                    t = it->second;
                    res += t;
                }
                f[i][j] += t + 1;
            }
        }
        return res;
    }
};