This is the 10th day of my participation in the August Text Challenge.More challenges in August

413. Division of arithmetic sequences

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. Example 2:

Input: nums = [1] Output: 0

Tip:

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

Their thinking

Dp [I] represents the number of arithmetic arrays with subscript I

State transition: if nums[I]-nums[i-1]==nums[i-1]-nums[i-2], the current nums[I] can be added to any array ending with nums[i-1], so dp[I]=dp[i-1]+1, because we have added a longer arithmetic array

code

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {

        int n=nums.length,res=0;
        int[] dp = new int[n];

        for(int i=2; i<n; i++) {if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2])
        {
            dp[i]=dp[i-1] +1; res+=dp[i]; }}returnres; }}Copy the code

Optimization idea

Because when writing the state transition equation, we find that dp[I] is only related to dp[i-1], we can maintain only one variable instead of an array, reducing the spatial complexity of n.

When the nums [I] – nums [I – 1)! =nums[i-1]-nums[i-2], we need to deal with the number of arithmetic array CNT, set it to 0, in dp the array initial value is 0, so we don’t need to deal with

code


class Solution {

        public int numberOfArithmeticSlices(int[] nums) {
            int n=nums.length,res=0,cnt=0;     

            for(int i=2; i<n; i++) {if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2])

                {
                   cnt++;

                }else cnt=0;

               res+=cnt;
            }
            returnres; }}Copy the code