446.Arithmetic Slices II - Subsequence
===

###### tags: `Hard`,`Array`,`DP`

[446. Arithmetic Slices II - Subsequence](https://leetcode.com/problems/arithmetic-slices-ii-subsequence/)

### 題目描述

Given an integer array `nums`, return *the number of all the **arithmetic subsequences** of* `nums`.

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, `[1, 3, 5, 7, 9]`, `[7, 7, 7, 7]`, and `[3, -1, -5, -9]` are arithmetic sequences.
* For example, `[1, 1, 2, 5, 7]` is not an arithmetic sequence.

A **subsequence** of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

* For example, `[2,5,10]` is a subsequence of `[1,2,1,2,4,1,5,10]`.

The test cases are generated so that the answer fits in **32-bit** integer.

### 範例

**Example 1:**

Input: nums = [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]

**Example 2:**

Input: nums = [7,7,7,7,7]
Output: 16
Explanation: Any subsequence of this array is arithmetic.

**Constraints**:

* `1 <= nums.length <= 1000`
* $-2^{31}$ <= `nums[i]` <= $2^{31} - 1$

### 解答
#### C++

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        vector<unordered_map<long long, int>> dp(n);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i-1; j >= 0; j--) {
                long long diff = (long long)nums[i] - (long long)nums[j];
                ans += dp[j][diff];
                dp[i][diff] += dp[j][diff] + 1;
            }
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Sun, Nov 27, 2022 8:49 PM]

#### Python

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [defaultdict(int) for _ in range(n)]
        ans = 0
        for i in range(1, n):
            for j in range(i):
                diff = nums[i] - nums[j]
                ans += dp[j][diff]
                dp[i][diff] += dp[j][diff] + 1
        return ans

> [name=Yen-Chi Chen][time=Sun, Nov 27, 2022 8:49 PM]

Time: $O(n^2)$
Extra Space: $O(n^2)$

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)