466. 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.

解題思路 #

直觀的想法是列舉所有子序列，列舉的過程判斷是否為等差。
難的點在紀錄序列，記錄每個序列的樣子太不切實際，可以改成紀錄每個等差對應的序列數量。
利用dp[i][diff]代表以arr[i]結尾，並且公差為diff的序列數量，可以歸納出以下式子。

// j for 0 to i-1
diff = nums[i]-nums[j]
dp[i][diff] += dp[j][diff] + 1

解法：DP #

c++

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

python

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