413. Arithmetic Slices
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.
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] <= 1000
From: LeetCode
Link: 413. Arithmetic Slices
Solution:
Ideas:
1. Initial Setup:
- We check if the array has fewer than 3 elements since at least 3 elements are required to form an arithmetic slice. If there are fewer than 3, we return 0.
2. Main Logic:
- We loop through the array starting from the third element (i = 2).
- For each triplet (nums[i-2], nums[i-1], nums[i]), we check if the difference between consecutive elements is the same (i.e., if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]).
- If they form an arithmetic sequence, we increment the currentStreak (which tracks how many consecutive arithmetic slices we have encountered). The total count is updated by adding the value of currentStreak.
- If the triplet does not form an arithmetic sequence, we reset the currentStreak to 0.
3. Return the Result:
- The total number of arithmetic slices is stored in count, which we return.
Code:
int numberOfArithmeticSlices(int* nums, int numsSize) {if (numsSize < 3) {return 0; // An arithmetic subarray needs at least 3 elements}int count = 0; // Total count of arithmetic slicesint currentStreak = 0; // The length of the current arithmetic slice streak// Loop through the array and check for arithmetic slicesfor (int i = 2; i < numsSize; i++) {// Check if the current subarray of 3 elements forms an arithmetic sequenceif (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {// If the current element continues an arithmetic slice, extend the current streakcurrentStreak++;count += currentStreak; // Add the current streak count to the total} else {// Reset the streak if the difference is not the samecurrentStreak = 0;}}return count;
}