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.
1function numberOfArithmeticSlices(nums) {
2 let n = nums.length;
3 if (n < 3) return 0;
4 let dp = 0, totalSlices = 0;
5 for (let i = 2; i < n; i++) {
6 if (nums[i] - nums[i - 1] === nums[i - 1] - nums[i - 2]) {
7 dp += 1;
8 totalSlices += dp;
9 } else {
10 dp = 0;
11 }
12 }
13 return totalSlices;
14}
15This JavaScript solution uses simple iteration and a counter to track the number of arithmetic slices ending at each position. It follows the dynamic programming strategy of maintaining and comparing differences during the loop.
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.
1public class Solution {
public int NumberOfArithmeticSlices(int[] nums) {
int n = nums.Length;
if (n < 3) return 0;
int totalSlices = 0;
for (int i = 0; i < n - 2; i++) {
int d = nums[i+1] - nums[i];
for (int j = i + 2; j < n; j++) {
if (nums[j] - nums[j-1] == d) {
totalSlices++;
} else {
break;
}
}
}
return totalSlices;
}
}
This C# solution marks similar logic and characteristics to other language implementations, focusing on validating and counting arithmetic slices through a strategic nested loop approach.