问题描述
给定一个数组，要求找出其中等差数列的子数组（连续元素构成的子数组）的个数。题目链接：**点我**
样例输入输出
输入：[1,2,3,4]
输出：3
解释：子数组为：[1,2,3]、[2,3,4]、[1,2,3,4]
输入：[1]
输出：0
问题解法
使用二维数组 dp[i][j] 表示由 i 到 j 构成的子数组是否是等差数列，如果是设置值为 true，否则设置为 false，最后遍历数组统计 true 的数量即为答案。代码如下
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
| class Solution {
public int numberOfArithmeticSlices(int[] nums) {
boolean[][] dp = new boolean[nums.length][nums.length];
for (int i = 2; i < nums.length; i++) {
if (nums[i - 1] - nums[i - 2] == nums[i] - nums[i - 1]) {
dp[i - 2][i] = true;
}
}
for (int i = 3; i < nums.length; i++) {
for (int j = 0; j < i - 2; j++) {
if (dp[j][i - 1] && nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
dp[j][i] = true;
}
}
}
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (dp[i][j]) {
count++;
}
}
}
return count;
}
}
|