Arithmetic Slices

Problem Statement

In the field of mathematics, particularly in sequences, an array is termed arithmetic if it meets two criteria: it contains at least three elements, and the difference between any two consecutive elements is constant across the sequence. Arrays such as [1,3,5,7,9], where each successive number increases by 2, or [7,7,7,7], where each element is identical thus resulting in a difference of 0, are classical examples of arithmetic arrays.

In this context, your task is to determine how many contiguous subarrays (a subarray is a subset of consecutive elements in the original array) in a given integer array nums, qualify as arithmetic. The challenge involves not only identifying these subarrays but understanding their formation based on sequence rules.

Examples

Example 1

Input:

nums = [1,2,3,4]

Output:

3

Explanation:

We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Example 2

Input:

nums = [1]

Output:

0

Constraints

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

Approach and Intuition

The goal is to determine the number of contiguous subarrays that are arithmetic in nature. Every valid subarray must adhere to the definition of an arithmetic sequence, having:

• At least three elements
• A consistent difference between consecutive elements

Given the examples:

• For the input nums = [1,2,3,4], subarrays such as [1, 2, 3], [2, 3, 4], or even [1,2,3,4] itself are all valid arithmetic subarrays, each showing a consistent difference of 1 between consecutive elements. This results in an output of 3.

• For the input nums = [1], no arithmetic subarrays are possible since a single element cannot form a sequence that meets the required criteria of at least three consecutive numbers.

To solve this problem:

1. Traverse the array and on each step, check if the current segment can extend a previously found arithmetic subarray. If a segment cannot be extended (i.e., the difference between consecutive elements changes), restart the count.
2. Use a count variable to maintain how many valid subsequences end at a position, and an answer variable to aggregate these into a total.
3. As you process and encounter valid arithmetic subarrays, add the size of possible subarrays to your total count result. For example, if a sequence of length 4 maintains the arithmetic property, it contains, in itself, three subarrays of size 3 (each offset by one element from the previous) and one subarray of size 4.

In terms of constraints, the solution approach should be efficient given the maximum possible array length (5000), making a nested loop approach potentially infeasible for the upper limits. Consideration of a linear or near-linear time complexity algorithm would be more appropriate to handle larger inputs effectively. The values of the elements (ranging between -1000 and 1000) do not directly complicate the approach since the concern primarily lies with the differences between them rather than their absolute values. The solution should ensure its correctness across the entire bounds of the array size, from the minimum of a single element (at which point no arithmetic subarrays are possible) to the maximum.

Solutions

public class Solution {
    public int calculateArithmeticSubarrays(int[] array) {
        int currentStreak = 0;
        int totalSequences = 0;
        for (int j = 2; j < array.length; j++) {
            if (array[j] - array[j - 1] == array[j - 1] - array[j - 2]) {
                currentStreak++;
            } else {
                totalSequences += currentStreak * (currentStreak + 1) / 2;
                currentStreak = 0;
            }
        }
        return totalSequences += currentStreak * (currentStreak + 1) / 2;
    }
}