05 August 2008
使用一个指针 j 从 i - 2 开始逆序地遍历数组的前缀部分 nums[0..i−2]：
已经求出了nums[i−1] 以及 nums[i] 作为等差数列的最后两项时，再增加一个数的情况下如何求出总的等差数列的和？
如果 nums[i]−nums[i+1]=d，那么在这一轮遍历中，j 会遍历到与上一轮相同的位置，答案增加的次数相同，并且额外多出了 nums[i−1],nums[i],nums[i+1] 这一个等差数列，所以只需要前面一个结果 + 1就可。
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
class Solution {
// dp[i] - 到i位置时的总数
// dp[i] = dp[i - 1] + 1 if distance is the same, otherwise start from 0
public int numberOfArithmeticSlices(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int len = nums.length;
int distance = nums[0] - nums[1];
int[] dp = new int[len];
int result = 0;
// 因为等差数列的长度至少为 3，所以可以从 i = 2 开始枚举, 0到1的距离上面已经算好
for (int i = 2; i < len; i++) {
if (nums[i - 1] - nums[i] == distance) {
dp[i] = dp[i - 1] + 1;
} else {
distance = nums[i - 1] - nums[i]; // 重新计算等差的差
// dp[i] = 0;
}
result += dp[i];
}
return result;
}
}
状态压缩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
if (nums == null || nums.length <= 1) {
return 0;
}
int len = nums.length;
int distance = nums[0] - nums[1]; //这里无所谓正负，后面循环里保持一致就行
int temp = 0;
int result = 0;
// 因为等差数列的长度至少为 3，所以可以从 i = 2 开始枚举, 0到1的距离上面已经算好
for (int i = 2; i < len; i++) {
if (nums[i - 1] - nums[i] == distance) {
temp++;
} else {
distance = nums[i - 1] - nums[i]; // 重新计算等差的差
temp = 0;
}
result += temp;
}
return result;
}
}