LeetCode413. Arithmetic Slices

题意

给定一个数组，求满足连续的相邻的元素的差值一样的子序列（至少3个元素）有多少个？
[1,2,3,4]->[1,2,3],[2,3,4],[1,2,3,4] 3个

思路

  1. 预处理数组相邻元素的差值
  2. 遍历找差值一样的片段

例如数组A为[1,2,3,4,6,7,8]
预处理后得到数组[1,1,1,2,1,1]
找到两个值相同的片段[1,1,1],[1,1]，长度分别为3和2
长度为n的片段代表有n+1个连续的元素差值相同，则长度大于等于3的子序列有∑(n-1)种

代码

第一次写的版本
缺陷：修改了原数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int ans = 0;
        int cnt = 1;
        for(int i = 0;i < A.length-1;i++){
            A[i]=A[i+1]-A[i];
            if(i!=0 && A[i]==A[i-1]) cnt++;
            else {
                if(cnt>=2) ans+=(cnt*(cnt-1))/2;
                cnt = 1;
            }
        }
        if(cnt>=2) ans+=(cnt*(cnt-1))/2;
        return ans;
    }
}

优化版本

1
2
3
4
5
6
7
8
9
10
11
public int numberOfArithmeticSlices(int[] A) {
    int curr = 0, sum = 0;
    for (int i=2; i<A.length; i++)
        if (A[i]-A[i-1] == A[i-1]-A[i-2]) {
            curr += 1;
            sum += curr;
        } else {
            curr = 0;
        }
    return sum;
}

留言

2017-01-26
⬆︎TOP