LeetCode 413 - Arithmetic Slices

作者 QIFAN 日期 2017-01-02
LeetCode 413 - Arithmetic Slices

原题链接:413. Arithmetic Slices


题干

算数切割(arithmetic slices)指的是一串至少含有 3 个元素的数字串,相邻两元素的差相同。

本题给定一个含有 n 数字的数组,返回满足算数切割的区间(i, j) 个数。

举例
输入:[1, 2, 3, 4]
返回:3
解释:[1, 2, 3] ,[2, 3, 4] ,[1, 2, 3, 4] 是算数切割。

思路

有两种思路。

1 排列组合法
找出当前的最长切割,算出其子集个数,再往后遍历计算。
输入:[1,2,3,4,6,8,9,10]
过程:
最长切割有[1,2,3,4],子集数为 $C_4^3 = 4$;及[8,9,10],子集数为 $C_3^3 = 1$ 。所以共有 5 个。

2 动态规划
前 i 个元素中的算数切割数与前 i + 1 个元素中的算术切割数有深切的联系。假设数组为 a
case 1: a[i - 1] , a[i] , a[i + 1] 是算数切割,如果 a[i] 与之前的元素也是一段算术切割,假设起始的 index 是 start ,则新加入的 a[i + 1] 会添加 i + 1 - index - 3 + 1 即 i - index - 1 个新切割。
case 2: a[i - 1] , a[i] , a[i + 1] 不是算数切割,那之前的连续就断了,i + 1 位置所含的算数切割数与 i 位置一样,start 变为 i 。
最后返回 index 为 a.length - 1 位置的切割数即可。

两种思路的时间复杂度都为 $O(n)$ ,空间复杂度为 $O(1)$ .

动态规划思路代码:

public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int lastSliceStart = 0;
int res = 0;
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
res = res + i + 1 - lastSliceStart + 1 - 3;
} else {
lastSliceStart = i - 1;
}
}
return res;
}