 # Division of arithmetic sequence of LeetCode dynamic programming

Posted on May 28, 2023, 12:44 a.m. by Gary Ingram
Category: The back-end

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

# The title

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 Description: NUMS has three subarithmetic arrays: [1,2,3, 3], [2, 3,4] and [1,2,3,4] itself.

Example 2: Input: nums =  Output: 0

1 = nums.length = 5000-1000 = nums[I] = 1000

## Analysis of the problem solving

1. To judge the boundary value, first of all, we need to judge the array length is greater than or equal to 3. Nums [I] = nums[I] = nums[I + 1] = nums[I + 1] = nums[I + 1] 3. For continuous data, we can use variable T to accumulate data and judge the order of the current sub-sequence; 4, finally accumulate the results to get the final answer.

Complexity analysis

• Time complexity: O(n)
• Space complexity: O(1)

## The problem solving code

The solution code is as follows (there are detailed notes in the code) :

``````class Solution {
public int numberOfArithmeticSlices(int[] nums) {
// Array length
int len = nums.length;
// Does not match the smallest array length
if (len  3) {
return 0;
}
// d is the difference of an arithmetic sequence
// t is the length of the cumulative continuous subarray
// ans is the return result
int d = nums - nums, t = 0, ans = 0;
for (int i = 2; i  len; i++) {
// If the arithmetic sequences are the same
if (nums[i] - nums[i - 1] == d) {
t++;
} else {
// If not
d = nums[i] - nums[i - 1];
// Clear the accumulation
t = 0;
}
ans += t;
}
returnans; }}Copy the code``````

Feedback results after submission: # The reference information

LeetCode 413: Arithmetic division

Search