Practice/Google/Leetcode 413. Arithmetic Slices

Leetcode 413. Arithmetic Slices

CodingMust

Problem

Given an integer array, determine how many contiguous subarrays form an arithmetic progression. An arithmetic progression is a sequence where the difference between every pair of consecutive elements is constant.

For a subarray to qualify, it must contain at least three elements. For example, [1, 3, 5] is an arithmetic progression with a common difference of 2, while [1, 2, 4] is not.

Your task is to count all such valid subarrays within the given array.

Requirements

1. Return the total count of arithmetic subarrays
2. Each subarray must have at least 3 elements
3. The difference between consecutive elements must be identical throughout the subarray
4. Consider all possible contiguous subarrays

Constraints

• 1 ≤ nums.length ≤ 5000
• -1000 ≤ nums[i] ≤ 1000
• Expected time complexity: O(n)
• Expected space complexity: O(1)

Examples

Example 1:

` Input: nums = [1, 2, 3, 4] Output: 3 Explanation: The arithmetic subarrays are:

• [1, 2, 3]
• [2, 3, 4]
• [1, 2, 3, 4] `

Example 2:

Input: nums = [1, 3, 5, 7, 9] Output: 6 Explanation: The entire array forms an arithmetic sequence. Valid slices: [1,3,5], [3,5,7], [5,7,9], [1,3,5,7], [3,5,7,9], [1,3,5,7,9]

Example 3:

Input: nums = [7, 7, 7, 7] Output: 3 Explanation: Common difference is 0. Valid slices: [7,7,7] (at positions 0-2), [7,7,7] (at positions 1-3), and [7,7,7,7]