Problem Description
Given an integer array, count the number of contiguous subarrays (called arithmetic slices) that have at least three elements and form an arithmetic sequence, meaning the difference between any two consecutive elements is constant.
Key Insights
- An arithmetic slice must have at least three elements.
- Instead of checking all possible subarrays, we can iterate through the array and count the number of valid arithmetic slices ending at each position.
- If three consecutive elements form an arithmetic sequence, then the number of arithmetic slices ending at the current index can be extended from the previous index.
- Use a dynamic programming or greedy strategy to build the solution in O(n) time.
Space and Time Complexity
Time Complexity: O(n) - We make a single pass through the array. Space Complexity: O(1) - Constant extra space is used.
Solution
We iterate through the array starting from the third element. For each index i, we check if the difference between nums[i] and nums[i-1] equals the difference between nums[i-1] and nums[i-2]. If it does, we know that the subarray ending at index i continues an arithmetic sequence. We use a variable (curr) to keep track of the number of arithmetic slices ending at the previous index and update it by adding one for the new valid slice in addition to extending previous ones. We then accumulate this count into our total result. When the sequence breaks, we reset the counter.