力扣每日一題2021-08-11等差數列劃分II - 子序列

文章目錄

• 446.等差數列劃分II - 子序列
• • 題目描述
  • 示例1
  • • 輸入
    • 輸出
    • 解釋
  • 示例2
  • • 輸入
    • 輸出
    • 解釋
  • 提示
  • 思路：暴力、動态規劃
  • • 動态規劃
    • • Python代碼

446.等差數列劃分II - 子序列

題目描述

給你一個整數數組nums，傳回nums中所有等差子序列的數目。

如果一個序列中至少有三個元素，并且任意兩個相鄰元素之差相同，則稱該序列為等差序列。

• 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7]、[3, -1, -5, -9]都是等差序列。

• 再例如，[1, 1, 2, 5, 7]不是等差序列。

  數組中的子序列是從數組中删除一些元素（也可能不删除）得到的一個序列。

• 例如，[2, 5, 10]是[1, 2, 1, 2, 4, 1, 5, 10]的一個子序列。

  題目資料保證答案是一個32-bit的整數。

示例1

輸入

nums = [2, 4, 6, 8, 10]

輸出

7

解釋

所有的等差子序列為：[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]

示例2

輸入

nums = [7, 7, 7, 7, 7]

輸出

16

解釋

數組中的任意子序列都是等差子序列。

提示

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231-1

思路：暴力、動态規劃

動态規劃

本題與昨天的題類似，隻不過昨天的題要求的是子數組，而今天的題要求的是子序列。

枚舉每兩個數的差，保證找到所有的等差序列。以[2, 4, 6, 8, 10]為例，第一輪假定等差數列從[2]開始周遊nums，第二個元素為4，公差為2， 則後續需要找到6，如果找到6，則所有6都可以構成等差數列，如果沒有找到6則[2, 4]開始的等差數列不成立，繼續以[2]為開頭繼續周遊。當[2]開頭的等差數列周遊完成後，開始周遊以[4]開頭的等差數列。直到所有nums中的數不足3個，停止周遊。但是用這樣的暴力搜尋會導緻逾時。

對于這個思路進行優化。假定依舊以[2]開始等差數列，後面的每個數和2的內插補點分别為[2, 4, 6, 8]，要找到等差序列，就要找到數組中每個數的後面有沒有[4+2, 6+4, 8+6, 10+8]。第二輪從4開始，後面的每個數和4的內插補點分别為[2, 4, 6]，如此周遊，即可得到結果。

Python代碼

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        # 動态規劃
        n = len(nums)
        ans = 0
        dp = [Counter() for i in range(n)]
        # 找到等差數列的末尾值
        for i in range(n-1):
            # 判斷加入值後，能不能構成等差數列
            for j in range(i+1, n):
                # 計算內插補點，作為公差
                diff = nums[j] - nums[i]
                # 如果前面這個末尾有以diff為差的等差序列，那麼j可以成為新的末尾，個數是它的個數+1，多了個[i, j]等差序列
                # 如果前面這個末尾沒有以diff為差的等差序列，那麼j和i構成一個等差序列的起始兩位，個數為(0+1)，後面有和j差為diff的話，就可以構成等差序列
                dp[j][diff] += dp[i][diff] + 1
                # i，j以及i前面的以diff為公差的等差序列，可以構成的新的等差序列
                ans += dp[i][diff]
        return ans