-
Notifications
You must be signed in to change notification settings - Fork 0
/
arithmetic-slices.h
39 lines (32 loc) · 835 Bytes
/
arithmetic-slices.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#ifndef ARITHMETIC_SLICES_H_
#define ARITHMETIC_SLICES_H_
#include <vector>
namespace solution {
int count(int c) {
auto result{0};
for (auto i{3}; i <= c; i++) {
result += c - i + 1;
}
return result;
}
int numberOfArithmeticSlices(std::vector<int>& nums) {
// sliding window...
// Runtime: 3 ms, faster than 66.63% of C++ online submissions for Arithmetic Slices.
// Memory Usage: 7.2 MB, less than 88.02% of C++ online submissions for Arithmetic Slices.
//
if (nums.size() < 3) return 0;
auto result{0}, c{2}, diff{nums[1] - nums[0]};
for (auto i{2}; i < nums.size(); ++i) {
if (diff == nums[i] - nums[i - 1]) {
++c;
} else {
result += count(c);
c = 2;
diff = nums[i] - nums[i - 1];
}
}
result += count(c);
return result;
}
}
#endif // ARITHMETIC_SLICES_H_