Description

Submission

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        unordered_map<int, vector<int>> val2idx;
        int n = nums.size();

        for(int i = 0; i < n; ++i) {
            val2idx[nums[i]].push_back(i);
        }

        vector<vector<int>> dp(n, vector<int>(n, 0));

        // nums[k] nums[j] nums[i]
        int ret = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < i; ++j) {
                long val = 2 * (long)nums[j] - nums[i];
                if(val > INT_MAX || val < INT_MIN) continue;
                for(auto k: val2idx[val]) {
                    if(k >= j) break;
                    dp[j][i] += dp[k][j] + 1;
                }
                ret += dp[j][i];
            }
        }

        return ret;
    }
};


// dp[i][j]: number of arithmetic subsequences ending with nums[i] then nums[j]