LeetCode 413 等差数列切片

1 题目描述

若一个数列至少有三个元素，且任意相邻两元素的差相等，则该数列为一个等差数列。

例如，如下三个数列即为等差数列：

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

如下数列不是等差数列：

1, 1, 2, 5, 7

现给定一个以0为起始索引，包含N个数的数组A。数组的切片(P, Q)为满足规则(0 <= P < Q < N)的任意整数组合。

若数组A的切片(P, Q)满足如下规则，则称该数组切片是一个等差数列：

A[P], A[p + 1], ..., A[Q - 1], A[Q]是一个等差数列，且P + 1 < Q。

代码函数需返回数组A的等差数列的个数。

例子：

输入：A = [1, 2, 3, 4]

输出：3

释义：A中有3个等差数列切片：[1, 2, 3]，[2, 3, 4]与[1, 2, 3, 4]。

题目出处：

https://leetcode.com/problems/arithmetic-slices/

2 解决思路

首先从A中找出有几个最长等差数列。

a）首先定义slices用来存储所有最长的等差slice，slice初始为2，初始间隔preInterval为a[1]-a[0]；

b）从第3个元素开始遍历A，若当前元素与前一个元素的差interval与preInterval相等，则slice+1；若interval与preInterval不等，则判断是否将当前slice合入slices，并将slice赋值为2，preInterval赋值为interval，遍历下一个元素；

c）直至遍历到最后一个元素，若interval与preInterval相等，则判断是否将当前slice合入slices。

对其中一个满足规则的最长等差数列，计算其中所有满足等差数列规则的切片个数的计算函数为。

func(slice int) int {
    if slice < 3 {
        return 0
    }
    num := 0
    for i := 3; i <= slice; i++ {
        num += (slice - i) + 1
    }
    return num
}

3 golang实现代码

综上，整个逻辑的实现代码为：

https://github.com/leileiluoluo/leetcode/blob/master/413_Arithmetic_Slices/test.go

func numberOfArithmeticSlices(a []int) int {
    if len(a) < 3 {
        return 0
    }

    slices := []int{}
    slice := 2
    preInterval := a[1] - a[0]
    for i := 2; i < len(a); i++ {
        interval := a[i] - a[i-1]
        if interval == preInterval {
            slice++
            if len(a)-1 == i && slice > 2 {
                slices = append(slices, slice)
            }
            continue
        }
        if slice > 2 {
            slices = append(slices, slice)
        }
        slice = 2
        preInterval = interval
    }

    f := func(slice int) int {
        if slice < 3 {
            return 0
        }
        num := 0
        for i := 3; i <= slice; i++ {
            num += (slice - i) + 1
        }
        return num
    }

    sum := 0
    for _, slice := range slices {
        sum += f(slice)
    }
    return sum
}

LeetCode 413 等差数列切片

相关文章

评论