requirements

If a sequence has at least three elements and any two adjacent elements are equally different, the number is said to be in an arithmetic sequence.

For example, [1,3,5,7,9], [7,7,7] and [3,-1,-5,-9] are arithmetic sequences. Given an integer array nums, return the number of all subarrays in nums that are arithmetic arrays.

A subarray is a contiguous sequence of arrays.

Example 1:

Input: nums = [1,2,3,4] Output: 3 Explanation: NUMS has three subarithmetic arrays: [1,2,3, 3], [2, 3,4] and [1,2,3,4] itself.Copy the code

Example 2:

Input: nums = [1] Output: 0Copy the code

Tip:

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

The core code

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) - >int:
        n = len(nums)
        if n < 3:
            return 0
        res = 0
        for l in range(0,n - 2):
            k,different = 2,nums[l + 1] - nums[l]
            for r in range(l + 2,n):
                if nums[r] - nums[r - 1] == different:
                    k += 1
                else:
                    break
            if k - 2> =1:
                res += k -2
        return res
Copy the code

Another solution

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) - >int:
        dp = [0 for _ in range(len(nums))]
        for i in range(2.len(nums)):
            if nums[i] - nums[i -1] == nums[i - 1] - nums[i - 2]:
                dp[i] = dp[i - 1] + 1
        return sum(dp)
Copy the code

Key issues

Answer:

The first solution: We use a loop, the first layer loops over the elements, the second layer loops over the arithmetic sequence, the extent to which the array increments,[2,3,4,5],[2,3,4,5,6],break, our k becomes 5,5. If we start with a 2 that doesn’t make an arithmetic sequence, we get the number of arithmetic sequences that can be made, This is the easy way. The second solution: using the idea of dynamic programming, see in accordance with the rule of the number of subarray statistics of this kind of problems, quickly can think of using dynamic programming to solve. Define the array dp with the same dimension as input A. dp[I] represents the number of arithmetic subarrays ending in A[I]. All elements in dp are initialized to zero because the number of arithmetic subarrays ending in A[I] is at least zero. If three consecutive elements ending in the array are arithmetic, a new arithmetic subarray is found, or the original arithmetic subarray continues to be extended. In this case, the number of arithmetic arrays ending in A[I] is the number of arithmetic subarrays ending in A[i-1] plus one. The recursive relation dp[I] = dp[i-1] + 1 is obtained. Finally, the sum of all elements in dp array is returned.