【LeetCode】413. Arithmetic Slices 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Python, DP
2. 解答2：
メモ・参考・感想

問題

原文

An integer array 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.

Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [1,2,3,4] Output: 3 Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

1
2
3

Input: nums = [1,2,3,4]
Output: 3
Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2:

Input: nums = [1] Output: 0

1
2

Input: nums = [1]
Output: 0

Constraints:

1 <= nums.length <= 5000

-1000 <= nums[i] <= 1000

内容

整数配列は、最低でも3つの要素があり、連続する要素の差が等しい場合にaithmeticと呼ばれます。

たとえば、[1,3,5,7,9]、[7,7,7,7]、[3,-1,-5,-9]です。

整数配列配列numsが与えられるので、numsのarithmeticな部分配列の数を返してください。

部分配列はnums内の連続する要素で構成される配列です。

※[1,2,3,4,5]であれば[1,3,5]のような間隔をあけた配列はarithmeticな配列ではない

必ず連続した要素で構成される

※正しくない可能性があります。

解答

解答1：Python, DP

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        #dp配列を用意。0で初期化
        dp = [0 for i in range(len(nums))]
        
        #条件を満たす配列の数をdp配列に記録
        #問題文より条件を満たす配列は3つの要素が必要なため3番目からスタート
        for i in range(2, len(nums)):
            #現在と1つ前の要素の差　＝　1つ前の要素と2つ前の要素の差　である場合
            if (nums[i] - nums[i-1]) == (nums[i-1] - nums[i-2]):
                #dp配列のi番目に1つ前の値に1を加えた値を記録
                #1つ前の要素の値は、そこまでに条件を満たす配列数を記録している
                #3番目の要素以降、条件を満たす配列は本当に必ず1つずつ増える？
                dp[i] = 1 + dp[i-1]
        
        return sum(dp)

class Solution:

def numberOfArithmeticSlices(self, nums: List[int]) -> int:

#dp配列を用意。0で初期化

dp = [0 for i in range(len(nums))]

#条件を満たす配列の数をdp配列に記録

#問題文より条件を満たす配列は3つの要素が必要なため3番目からスタート

for i in range(2, len(nums)):

#現在と1つ前の要素の差　＝　1つ前の要素と2つ前の要素の差　である場合

if (nums[i] - nums[i-1]) == (nums[i-1] - nums[i-2]):

#dp配列のi番目に1つ前の値に1を加えた値を記録

#1つ前の要素の値は、そこまでに条件を満たす配列数を記録している

#3番目の要素以降、条件を満たす配列は本当に必ず1つずつ増える？

dp[i] = 1 + dp[i-1]

return sum(dp)

解答2：

メモ・参考・感想

前：62. Unique Paths

次：300. Longest Increasing Subsequence

LeetCode 解答・解説記事一覧