Arithmetic Slices II - Subsequence
Hard · Dynamic Programming · Array · Dynamic Programming · Hash Table
Problem
Given an integer array nums, return the number of arithmetic subsequences in it.
A subsequence is arithmetic if it has at least three elements and every pair of consecutive elements has the same difference. Subsequences are identified by the indices they use, so equal-valued subsequences at different positions count separately.
The answer fits in a signed 32-bit integer.
Examples
Input: nums = [1,2,3,4] Output: 3
They are [1,2,3], [2,3,4] and [1,2,3,4].
Input: nums = [3,3,3,3] Output: 5
Any 3 or 4 of the positions work: C(4,3) + C(4,4) = 5.
Input: nums = [2,4,6,8,10] Output: 7
Difference 2: three of length 3, two of length 4 and one of length 5. Difference 4: [2,6,10]. Seven in all.
Constraints
- 1 <= len(nums) <= 1000
- -2^31 <= nums[i] <= 2^31 - 1
Approaches
- Baseline: table over the last two indices — time O(n³), space O(n²)
Follow-up
Why count sequences of length two or more rather than three or more? (A length-3 sequence is built from a length-2 one, so the pairs have to be tracked anyway; the answer just never adds the bare pairs.)
Related problems
Start free on Cariara · Coding problems · System design studio
