频道栏目
首页 > 考试 > 其他 > 正文

LeetCode 413 Arithmetic Slices (找等差数列)

2016-11-01 09:25:32      个评论    来源:Tc_To_Top的专栏  
收藏   我要投稿

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.

 

题目链接:https://leetcode.com/problems/arithmetic-slices/


题目分析:直接从头开始找等差数列,假设有一段等差数列的长度为n (n >= 3),则其包含的等差数列个数是(n-2)*(n-2+1)/2,所以直接扫一下即可,时间复杂度O(n)
public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int pos = 0, ans = 0, sz = A.length;
        while (pos + 2 < sz) {
            int d = A[pos + 1] - A[pos], num = 2;
            int tmp = pos + 2;
            while (tmp < sz && A[tmp] - A[tmp - 1] == d) {
                num ++;
                tmp ++;
            }
            if (num > 2) {
                ans += (num - 2) * (num - 1) / 2;
                pos = tmp;
            }
            else {
                pos ++;
            }
        }
        return ans;
    }
}

其实可以直接简写成这样
public class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int sz = A.length, cur = 0, sum = 0;
        for (int i = 1; i < sz - 1; i ++) {
            if (A[i] - A[i - 1] == A[i + 1] - A[i]) {
                cur ++;
                sum += cur;
            }
            else {
                cur = 0;
            }
        }
        return sum;
    }
}

相关TAG标签 LeetCode
上一篇:LeetCode:Add Strings
下一篇:LeetCode 167 Two Sum II - Input array is sorted (两点法)
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站