[leetcode]--413. Arithmetic Slices

刺骨的言语ヽ痛彻心扉 2022-07-11 23:24 128阅读 0赞

Question 413. Arithmetic Slices

> 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.

下面是我理解的一个思路：  
i) 题目要求最少有3个连续等差的序列；  
ii) 所以我们从索引位置2开始，如果我们得到index位置与前面两个数等差就获得了一个结果。  
iii)在索引位置i处，如果和前面的序列组成了一个结果， 那意味着curr扩展到了index位置。同时我们获得到了一和序列，因此curr自加。

实现源代码：

public static int numberOfArithmeticSlices(int[] A) {
        int curr=0;//每次计数的保存值
        int sum=0;//计数最后总的序列个数
    
        for(int i=2; i<A.length; i++){
            if(A[i]-A[i-1] == A[i-1]-A[i-2]){
                curr++;
                sum += curr;
            }else {
                curr=0;
            }
        }
    
        return sum;
    }

测试代码：

public static void main(String[] args) {
        int[] A = {
       1,2,3,4,8,9,10};
        int result = numberOfArithmeticSlices(A);
        LogUtil.log_debug("result: "+result);
    }

运行结果：

2017-02-05 14:23:46：result: 4