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.