“This is the 17th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Although there are still several days left in the holiday, I feel more and more strongly that there is not enough time. Every day in Leetcode, one day passes quickly without doing several exercises. I can only tell myself to take it slowly, and there may be some breakthroughs after a period of time.

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 = [1] Output: 0

Train of thought

At first, I considered using DP to do it, but after I finished it, I saw other people’s methods on the Internet and found it was good, so I tried to do it myself. A subarray is a continuous sequence of arrays. This limits the number of skipped elements, so we can just double differentiate the adjacent elements of the array and store them in an array ds, which should have the same length as len-1. Because each arithmetic sequence requires at least 3 elements, that is, at least 2 consecutive identical differences in DS. So if I have count, how many arithmetic sequences do I have? We can deduce that n consecutive identical differences correspond to n+1 elements of the original array:

  • Length 3: The start element ranges from 0 to count-2 and the quantity is count-1
  • Length 4: The start element ranges from 0 to count-3, and the quantity is count-2
  • .
  • Length count: The starting element is 0 and the quantity is 1

So, the total number of corresponding arithmetic sequences is the sum of order n minus one, which is the Gauss sum formula

(count-1)*count/2
Copy the code

So, let’s go through the DS array, find count of consecutive identical differences and use the formula above to figure out the number of arithmetic sequences, and sum up to get the solution.

Java version code

class Solution { public int numberOfArithmeticSlices(int[] nums) { int len = nums.length; if (len < 3) { return 0; } int[] ds = new int[len-1]; For (int I = 0; i < len - 1; i++) { ds[i] = nums[i+1] - nums[i]; } int ans = 0; int count = 1; for (int i = 1; i < len - 1; i++) { if (ds[i] == ds[i-1]) { count++; } else { if (count >= 2) { ans += (count-1) * count / 2; } count = 1; } } if (count >= 2) { ans += (count-1) * count / 2; } return ans; }}Copy the code