446. Arithmetic Slices II - Subsequence

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.

A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

Example:

Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[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]

如果類似413. Arithmetic Slices的DP概念維護一個1D DP array，那麼我們無法把不同的difference給考慮進去，所以我們需要一個更高維度的dp data container來幫助紀錄運算。但數字間的差值沒有像index一樣有限制，所以無法使用2D array來做，可用一維的hashmap來做。vector的index就是input A裡的index，hashmap的key是數字間的差，value就是這之前有幾個這樣的差。 外層for loop掃描所有可能的i，內層for loop掃描小於i的所有j，這時會得到一個diff，如果發現dp[j]已經有diff的key，那代表j之前相差diff的數、j代表的數、i代表的數可以形成一個等差數列，因為至少包含3個數，所以可以加上res。然後要把dp[j][diff]加到dp[i][diff]更新，等於i代表的數跟前面在j代表的數結尾的等差數列結合。

// Dynamic Programming
int numberOfArithmeticSlices(vector<int>& A) { // time: O(n^2); space: O(n^2)
    int res = 0, n = A.size();
    vector<unordered_map<int, int> > dp(n); // index -> <diff, cnt>
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            long delta = (long)A[i] - A[j];
            if (delta < INT_MIN || delta > INT_MAX) continue;
            int diff = (int)delta;
            ++dp[i][diff];
            if (dp[j].count(diff)) {
                res += dp[j][diff];
                dp[i][diff] += dp[j][diff];
            }
        }
    }
    return res;
}

413. Arithmetic Slices