Sponsored
Sponsored
The 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.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), using only constant space.
1public class Solution {
2 public int numberOfArithmeticSlices(int[] nums) {
3 int n = nums.length;
4 if (n < 3) return 0;
5 int dp = 0, totalSlices = 0;
6 for (int i = 2; i < n; i++) {
7 if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
8 dp += 1;
9 totalSlices += dp;
10 } else {
11 dp = 0;
12 }
13 }
14 return totalSlices;
15 }
16}
17This Java solution follows the same logic as the Python one. It maintains a variable name dp for counting the subarrays ending at each index that are arithmetic. On each match of difference, dp is increased, and it's reset on a mismatch.
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.
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.
1defThis 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.