Arithmetic Slices
A sequence of numbers is called an arithmetic sequence if the difference between any two successive members is constant. An arithmetic slice is a sequence of at least 3 numbers that form an arithmetic sequence. Given an array of integers, return the number of arithmetic slices in the array.
Constraints:
- 1 <= nums.length <= 500
- -10000 <= nums[i] <= 10000
Examples:
Input: [1, 2, 3, 4]
Output: 3
Explanation: The arithmetic slices are [1, 2, 3], [2, 3, 4], and [1, 2, 3, 4].
Input: [1, 2, 3, 5, 7, 9]
Output: 2
Explanation: The arithmetic slices are [1, 2, 3] and [5, 7, 9].
Solutions
Dynamic Programming
This solution uses dynamic programming to count the number of arithmetic slices. It iterates over the array and for each element, it checks if the next elements form an arithmetic sequence. If they do, it increments the count.
int numberOfArithmeticSlices(vector<int>& nums) {
int count = 0;
for (int i = 0;
i < nums.size() - 2;
i++) {
int diff = nums[i + 1] - nums[i];
int j = i + 2;
while (j < nums.size() && nums[j] - nums[j - 1] == diff) {
count++;
j++;
}
}
return count;
}Follow-up:
What if the array can contain duplicate elements?
