446. Arithmetic Slices II - Subsequence

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/

• 先卡位，今天打疫苗，开始发烧了
• 9/11补上

题目解释

你会得到一组阵列，请从阵列中找出所有可以组成的等差数列，但是有以下条件:

1. 等差数列的要包含至少3个数字
2. 必须按照阵列数字原有的顺序找出等差数列

example

解法

这题我觉得很难，看着别人的答案只觉得，能想到这个解法的不是人吧!

所以我尽量用浅显易懂的方式说明别人的解法

先看看程序码吧

程序码

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

这题要用动态规划(dp)来解，而dp要记录的东西请看下图

表格的y 方向是阵列的所有数字，表格的x 方向纪录数字之间会出现的差

而表格内的数字则代表到目前为止，有包含该数字的等差数列有几个

例如:

上图中:
(阵列4，差2)的数字就代表数字4在目前组出等差为2的数列出现1次 --> [2,4]
(阵列6，差2)的数字就代表数字6在目前组出等差为2的数列出现2次 --> [2,4,6]、[4,6]
(阵列8，差2)的数字就代表数字8在目前组出等差为2的数列出现3次 --> [2,4,6,8]、[4,6,8]、[6,8]

这些步骤就是这段程序在做的

difference = nums[i] - nums[j]
dp[i][difference] += dp[j][difference] + 1

而我们要回传有几组符合条件的，则靠这行程序去纪录:

ans += dp[j][difference]

这行的意思我们再借用上图来解释:

(阵列6，差2)的数字就代表数字6在目前组出等差为2的数列出现2次 --> [2,4,6]、[4,6]
(阵列8，差2)的数字就代表数字8在目前组出等差为2的数列出现3次 --> [2,4,6,8]、[4,6,8]、[6,8]

当我们再计算(阵列8，差2)的数字是多少时，这里ans 会记录(阵列6，差2)里的2

这代表数字8让*[2,4,6]、[4,6]* 变成*[2,4,6,8]、[4,6,8]*，所以我们纪录(阵列6，差2)里的2

闲聊

还在发烧中