446. 等差数列划分 II - 子序列 2021-08-11

class Solution {
private:
    unordered_map<long long, vector<int> > m;
    vector<int> nums;
    vector<unordered_map<long long, int> > cache;
    int DFS(int start, long long diff) {
        if (cache[start].count(diff))
            return cache[start][diff];
        long long target = (long long) nums[start] + diff;
        auto it = m.find(target);
        int count = 0;
        if (it != m.end()) {
            auto &positions = it->second;
            auto pos_it = upper_bound(positions.begin(), positions.end(), start);
            count += (positions.end() - pos_it);
            while (pos_it != positions.end()) {
                count += DFS(*pos_it, diff);
                ++pos_it;
            }
        }
        cache[start][diff] = count;
        return count;
    }
public:
    int numberOfArithmeticSlices(vector<int> &nums_) {
        nums = nums_;
        cache.resize(nums.size());
        for (int i = 0; i < nums.size(); ++i) {
            m[nums[i]].push_back(i);
        }
        int count = 0;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                count += DFS(j, (long long) nums[j] - nums[i]);
            }
        }
        return count;
    }
};

时间复杂度不超过