An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
[1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.Given an integer array nums, return the number of arithmetic subarrays of nums.
A subarray is a contiguous subsequence of the array.
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] <= 1000The idea is to use dynamic programming to count the number of arithmetic subarrays ending at each position in the array. By traversing from the start to the end of the array, we can keep track of how many arithmetic subarrays end at each index by considering the difference of current and previous elements.
This Python solution iterates through the array starting from the third element. It uses a variable dp to keep track of the number of subarrays ending at the current index that are arithmetic. If the difference between the current element and the previous element is the same as the previous difference, dp is incremented. Otherwise, it is reset to zero. The result is accumulated in total_slices.
Java
C++
C#
JavaScript
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), using only constant space.
This approach uses a double loop to consider all subarrays of length greater than or equal to 3. A sliding window technique checks each possible subarray in fewer operations. This approach is less optimal in terms of time complexity compared to dynamic programming, but it provides a clear and direct method to check subarrays.
This solution calculates the difference between every two consecutive elements d and checks if the subsequent elements maintain this difference. If they do, it increments the count of arithmetic subarrays. It stops the inner loop early if the difference condition breaks, optimizing from the naive complete enumeration.
Java
C++
C#
JavaScript
Time Complexity: O(n^2) in the worst case, because we loop through pairs of start and end indices with an early exit.
Space Complexity: O(1), using constant extra space.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n), where n is the length of the array. |
| Iterative Check with Sliding Window | Time Complexity: O(n^2) in the worst case, because we loop through pairs of start and end indices with an early exit. |
Arithmetic Slices • Pepcoding • 18,296 views views
Watch 9 more video solutions →Practice Arithmetic Slices with our built-in code editor and test cases.
Practice on FleetCode