413. Arithmetic Slices #

Problem #

A sequence of numbers 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 sequences:

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

Problem Summary #

Array A contains N numbers, and its indices start from 0. A subarray slice of array A is represented as (P, Q), where P and Q are integers satisfying 0<=P<Q<N. If the following condition is met, the subarray (P, Q) is called an arithmetic array: the elements A[P], A[p + 1], …, A[Q - 1], A[Q] are arithmetic. And P + 1 < Q. The function should return the number of all subarrays in array A that are arithmetic arrays.

Solution Approach #

• According to the definition given in the problem, only arithmetic sequences with at least 3 numbers satisfy the requirement. For k consecutive elements that form an arithmetic sequence, the number of arithmetic subsequences contained in them is incremental: 1, 2, 3, … k. Therefore, each time we check a group of 3 consecutive numbers, we only need to use one variable to accumulate how many consecutive elements before it already satisfy the requirement. As long as the arithmetic sequence satisfies the requirement, add this accumulated value. Once the arithmetic condition is not satisfied, reset the accumulated value to 0. In this way, a single loop can find the answer required by the problem.

Code #

package leetcode

func numberOfArithmeticSlices(A []int) int {
	if len(A) < 3 {
		return 0
	}
	res, dp := 0, 0
	for i := 1; i < len(A)-1; i++ {
		if A[i+1]-A[i] == A[i]-A[i-1] {
			dp++
			res += dp
		} else {
			dp = 0
		}
	}
	return res
}