题目描述
如果一个数列 至少有三个元素 ,并且任意两个相邻元素之差相同,则称该数列为等差数列。
- 例如,
[1,3,5,7,9]
、[7,7,7,7]
和 [3,-1,-5,-9]
都是等差数列。
给你一个整数数组 nums
,返回数组 nums
中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
示例 1:
输入:nums = [1,2,3,4]
输出:3
解释:nums 中有三个子等差数组:[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
示例 2:
输入:nums = [1]
输出:0
提示:
1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000
解法
方法一:遍历计数
我们用 $d$ 表示当前相邻两个元素的差值,用 $cnt$ 表示当前等差数列的长度,初始时 $d = 3000$, $cnt = 2$。
遍历数组 nums
,对于相邻的两个元素 $a$ 和 $b$,如果 $b - a = d$,则说明当前元素 $b$ 也属于当前等差数列,此时 $cnt$ 自增 1;否则说明当前元素 $b$ 不属于当前等差数列,此时更新 $d = b - a$,$cnt = 2$。如果 $cnt \ge 3$,则说明当前等差数列的长度至少为 3,此时等差数列的个数为 $cnt - 2$,将其加到答案中。
遍历结束后,即可得到答案。
在代码实现上,我们也可以将 $cnt$ 初始化为 $0$,重置 $cnt$ 时,直接将 $cnt$ 置为 $0$;累加答案时,直接累加 $cnt$ 即可。
时间复杂度 $O(n)$,空间复杂度 $O(1)$。其中 $n$ 是数组 nums
的长度。
相似题目:
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
ans, cnt = 0, 2
d = 3000
for a, b in pairwise(nums):
if b - a == d:
cnt += 1
else:
d = b - a
cnt = 2
ans += max(0, cnt - 2)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public int numberOfArithmeticSlices(int[] nums) {
int ans = 0, cnt = 0;
int d = 3000;
for (int i = 0; i < nums.length - 1; ++i) {
if (nums[i + 1] - nums[i] == d) {
++cnt;
} else {
d = nums[i + 1] - nums[i];
cnt = 0;
}
ans += cnt;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int ans = 0, cnt = 0;
int d = 3000;
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i + 1] - nums[i] == d) {
++cnt;
} else {
d = nums[i + 1] - nums[i];
cnt = 0;
}
ans += cnt;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | func numberOfArithmeticSlices(nums []int) (ans int) {
cnt, d := 0, 3000
for i, b := range nums[1:] {
a := nums[i]
if b-a == d {
cnt++
} else {
d = b - a
cnt = 0
}
ans += cnt
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | function numberOfArithmeticSlices(nums: number[]): number {
let ans = 0;
let cnt = 0;
let d = 3000;
for (let i = 0; i < nums.length - 1; ++i) {
const a = nums[i];
const b = nums[i + 1];
if (b - a == d) {
++cnt;
} else {
d = b - a;
cnt = 0;
}
ans += cnt;
}
return ans;
}
|
方法二