413. Arithmetic Slices
1. Description
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.
- For example, [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.
2. Example
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
3. Constraints
- 1 <= nums.length <= 5000
- -1000 <= nums[i] <= 1000
4. Solutions
Two Pointers
n = nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
int numberOfArithmeticSlices(const vector<int> &nums) {
cin.tie(nullptr);
ios::sync_with_stdio(false);
if (nums.size() == 1) {
return 0;
}
int result = 0;
int left = 0, right = 1, diff_count = 0;
for (int diff = nums[right] - nums[left]; right < nums.size();) {
if (nums[right] - nums[right - 1] != diff) {
result += count_slices_(left, right, diff_count);
++left;
diff = nums[right] - nums[left];
diff_count = 0;
} else {
++right;
++diff_count;
}
}
result += count_slices_(left, right, diff_count);
return result;
}
private:
int count_slices_(int left, int right, int diff_count) {
return diff_count > 1 ? (right - left) * (right - left - 1) / 2 : 0;
}
};