Array
Dynamic Programming
Description
Given an integer array nums
, return the number of all the arithmetic subsequences of nums
.
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, [1, 3, 5, 7, 9]
, [7, 7, 7, 7]
, and [3, -1, -5, -9]
are arithmetic sequences.
For example, [1, 1, 2, 5, 7]
is not an arithmetic sequence.
A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.
For example, [2,5,10]
is a subsequence of [1,2,1,2 ,4,1,5 ,10 ]
.
The test cases are generated so that the answer fits in 32-bit integer.
Example 1:
Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
Example 2:
Input: nums = [7,7,7,7,7]
Output: 16
Explanation: Any subsequence of this array is arithmetic.
Constraints:
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
Solutions
Solution 1
Python3 Java C++ Go TypeScript
class Solution :
def numberOfArithmeticSlices ( self , nums : List [ int ]) -> int :
f = [ defaultdict ( int ) for _ in nums ]
ans = 0
for i , x in enumerate ( nums ):
for j , y in enumerate ( nums [: i ]):
d = x - y
ans += f [ j ][ d ]
f [ i ][ d ] += f [ j ][ d ] + 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public int numberOfArithmeticSlices ( int [] nums ) {
int n = nums . length ;
Map < Long , Integer >[] f = new Map [ n ] ;
Arrays . setAll ( f , k -> new HashMap <> ());
int ans = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < i ; ++ j ) {
Long d = 1L * nums [ i ] - nums [ j ] ;
int cnt = f [ j ] . getOrDefault ( d , 0 );
ans += cnt ;
f [ i ] . merge ( d , cnt + 1 , Integer :: sum );
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public :
int numberOfArithmeticSlices ( vector < int >& nums ) {
int n = nums . size ();
unordered_map < long long , int > f [ n ];
int ans = 0 ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = 0 ; j < i ; ++ j ) {
long long d = 1L L * nums [ i ] - nums [ j ];
int cnt = f [ j ][ d ];
ans += cnt ;
f [ i ][ d ] += cnt + 1 ;
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 func numberOfArithmeticSlices ( nums [] int ) ( ans int ) {
f := make ([] map [ int ] int , len ( nums ))
for i := range f {
f [ i ] = map [ int ] int {}
}
for i , x := range nums {
for j , y := range nums [: i ] {
d := x - y
cnt := f [ j ][ d ]
ans += cnt
f [ i ][ d ] += cnt + 1
}
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 function numberOfArithmeticSlices ( nums : number []) : number {
const n = nums . length ;
const f : Map < number , number > [] = new Array ( n ). fill ( 0 ). map (() => new Map ());
let ans = 0 ;
for ( let i = 0 ; i < n ; ++ i ) {
for ( let j = 0 ; j < i ; ++ j ) {
const d = nums [ i ] - nums [ j ];
const cnt = f [ j ]. get ( d ) || 0 ;
ans += cnt ;
f [ i ]. set ( d , ( f [ i ]. get ( d ) || 0 ) + cnt + 1 );
}
}
return ans ;
}
GitHub