Double pointer solution to arithmetic division

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

Topic describes

This is the 413 arithmetic division on LeetCode. The difficulty is medium.

Tag: “Dual pointer”, “analog”, “math”

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

Double pointer

Specifically, we can enumerate iii as the left endpoint of the subarray of difference DDD, and then find the right endpoint JJJ of the current isometric and longest subarray by “double-pointer” method. Let the interval [I,j][I,j][I,j][I,j] be lenlenlen.

So obviously, the number of subarrays that meet the criteria is:

The function int countWithArrayLength(int k) finds the number of subarrays of length KKK.

It is not difficult to find that the return value of the function increases gradually as the input parameter KKK decreases gradually.

Therefore, the above result, CNTCNTCNT, is actually the sum of an arithmetic sequence with the beginning term of 111 and the end term of len−3+ 1len-3 +1len −3+1 tolerance of 111. Directly apply “arithmetic sequence sum” formula can be solved.

Code:

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n - 2;) {int j = i, d = nums[i + 1] - nums[i];
            while (j + 1 < n && nums[j + 1] - nums[j] == d) j++;
            int len = j - i + 1;
            // a1: the number of subarrays with length len; An: number of subarrays of length 3
            int a1 = 1, an = len - 3 + 1;
            // The number of subarrays that match the condition (length greater than or equal to 3) is the result of "sum of difference sequences"
            int cnt = (a1 + an) * an / 2;
            ans += cnt;
            i = j;
        }
        returnans; }}Copy the code

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

The last

This is the No.413 article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks, we will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.