1.題目大意

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.

剛開始看這道題的時(shí)候我還挺糾結(jié)的，然后發(fā)現(xiàn)其實(shí)是我對題意的理解有問題，或者說題目本身sample給的也不好。

(1)首先，題目輸入的數(shù)列是0索引的數(shù)組，注意，這個(gè)輸入的數(shù)組的各個(gè)數(shù)字不一定是等差數(shù)列，比如說可能輸入的是{1,2,5,6}。

(2)所求的P+1<Q，也就是說所求出的等比數(shù)列中至少包含3個(gè)元素，比如{1,2,3,4}中{1,2}就不算是arithmetic。

(3)所求的arithmetic在原數(shù)組中要求是位置連續(xù)的，比如原數(shù)組若給定的是{1,2,4,3}，這里的{1,2,3}在原數(shù)組中并不連續(xù)，因此會返回0。而{1,3,5,6}中{1,3,5}位置則是連續(xù)的。

再舉幾個(gè)例子：

輸入：{1,2} 返回0 。因?yàn)闆]有3個(gè)以上的元素。

輸入：{1,3,5,6,7} 返回2。因?yàn)橛衶1,3,5}和{5,6,7}。而{1,3,5,7}則不算，因?yàn)樗鼈冊谠瓟?shù)組里不連續(xù)。

輸入：{1,3,5} 返回1。

?

2.思路

顯而易見：連續(xù)的等差數(shù)列有n個(gè)元素的時(shí)候，則會有(1+2+...+n)個(gè)等差子數(shù)列。

{1,2,3} ->?{1,2,3} ->1

{1,2,3,4} ->?{1,2,3,4} +?{1,2,3} +?{2,3,4}?-> 1+2 ->3

{1,2,3,4,5} ->?{1,2,3,4,5} +?{1,2,3,4} +?{2,3,4,5} +?{1,2,3} +?{2,3,4} + {3,4,5} -> 1+2+3 ->6

{1,2,....,n} -> ...... -> 1+2+...+n ?

?

3.代碼

public:int numberOfArithmeticSlices(vector<int>& A) {int sum=0,count=1;if(A.size()<3) return 0;for(int i=1;i<A.size()-1;i++){if(A[i]-A[i-1]==A[i+1]-A[i]) sum+=(count++);elsecount=1;}return sum;} };

　　

轉(zhuǎn)載于:https://www.cnblogs.com/rgvb178/p/5967894.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode - 413. Arithmetic Slices - 含中文题意解释 - O(n) - ( C++ ) - 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。