413. Arithmetic Slices （找等差数列）

àì夳堔傛蜴生んèń 2022-07-15 08:14 132阅读 0赞

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
    7, 7, 7, 7
    3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:  
A\[P\], A\[p + 1\], ..., A\[Q - 1\], A\[Q\] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]
    
    return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

题目大意：找到给定数组中所有 **元素个数大于等于3** 的等差数列，计算所有满足条件的数列的数量。

解题思路：观察下表，发现当等差数列中 **元素个数 **为3时，其中包含的 **子等差数列** 个数为1；**元素个数**为4时，**子等差数列  **个数为3；**元素个数**为5时，**子等差数列  **个数为6 ... 子等差数列数量之差分别为2、3、4 ... 那么我们就可以根据这个规律来计算，初始结果数res = 0，置num=1，当找到 元素个数为3的等差数列 时，res += num，令num++，如果后面的一个元素可以加入到该等差数列中，则 res += num，num++ ... 当发现某一元素不满足当前等差数列，则重置num = 1 。直到遍历完整个数组。

序列                个数        差值
    1 2 3               1         
    1 2 3 4             3           2
    1 2 3 4 5           6           3
    1 2 3 4 5 6         10          4

代码如下：（2ms，beats 34.05%）

public int numberOfArithmeticSlices(int[] A) {
            if (A.length < 3)
    			return 0;
    		int res = 0, i, dif = A[1] - A[0], k = 2, n = A.length, num = 1;
    		for (i = 2; i < n; i++) {
    			if (A[i] - A[i - 1] == dif) {
    				res += num++;
    			} else {
    				dif = A[i] - A[i - 1];
    				num = 1;
    			}
    		}
    		return res;
        }