Array
Hash Table
Sliding Window
Description
You are given an array nums
consisting of positive integers.
We call a subarray of an array complete if the following condition is satisfied:
The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.
Return the number of complete subarrays .
A subarray is a contiguous non-empty part of an array.
Example 1:
Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].
Example 2:
Input: nums = [5,5,5,5]
Output: 10
Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 2000
Solutions
Solution 1
Solution 2
Python3 Java C++ Go TypeScript Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution :
def countCompleteSubarrays ( self , nums : List [ int ]) -> int :
cnt = len ( set ( nums ))
d = Counter ()
ans , n = 0 , len ( nums )
i = 0
for j , x in enumerate ( nums ):
d [ x ] += 1
while len ( d ) == cnt :
ans += n - j
d [ nums [ i ]] -= 1
if d [ nums [ i ]] == 0 :
d . pop ( nums [ i ])
i += 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public int countCompleteSubarrays ( int [] nums ) {
Map < Integer , Integer > d = new HashMap <> ();
for ( int x : nums ) {
d . put ( x , 1 );
}
int cnt = d . size ();
int ans = 0 , n = nums . length ;
d . clear ();
for ( int i = 0 , j = 0 ; j < n ; ++ j ) {
d . merge ( nums [ j ] , 1 , Integer :: sum );
while ( d . size () == cnt ) {
ans += n - j ;
if ( d . merge ( nums [ i ] , - 1 , Integer :: sum ) == 0 ) {
d . remove ( nums [ i ] );
}
++ i ;
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public :
int countCompleteSubarrays ( vector < int >& nums ) {
unordered_map < int , int > d ;
for ( int x : nums ) {
d [ x ] = 1 ;
}
int cnt = d . size ();
d . clear ();
int ans = 0 , n = nums . size ();
for ( int i = 0 , j = 0 ; j < n ; ++ j ) {
d [ nums [ j ]] ++ ;
while ( d . size () == cnt ) {
ans += n - j ;
if ( -- d [ nums [ i ]] == 0 ) {
d . erase ( nums [ i ]);
}
++ i ;
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 func countCompleteSubarrays ( nums [] int ) ( ans int ) {
d := map [ int ] int {}
for _ , x := range nums {
d [ x ] = 1
}
cnt := len ( d )
i , n := 0 , len ( nums )
d = map [ int ] int {}
for j , x := range nums {
d [ x ] ++
for len ( d ) == cnt {
ans += n - j
d [ nums [ i ]] --
if d [ nums [ i ]] == 0 {
delete ( d , nums [ i ])
}
i ++
}
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 function countCompleteSubarrays ( nums : number []) : number {
const d : Map < number , number > = new Map ();
for ( const x of nums ) {
d . set ( x , ( d . get ( x ) ?? 0 ) + 1 );
}
const cnt = d . size ;
d . clear ();
const n = nums . length ;
let ans = 0 ;
let i = 0 ;
for ( let j = 0 ; j < n ; ++ j ) {
d . set ( nums [ j ], ( d . get ( nums [ j ]) ?? 0 ) + 1 );
while ( d . size === cnt ) {
ans += n - j ;
d . set ( nums [ i ], d . get ( nums [ i ]) ! - 1 );
if ( d . get ( nums [ i ]) === 0 ) {
d . delete ( nums [ i ]);
}
++ i ;
}
}
return ans ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 use std :: collections :: HashMap ;
use std :: collections :: HashSet ;
impl Solution {
pub fn count_complete_subarrays ( nums : Vec < i32 > ) -> i32 {
let n = nums . len ();
let m = nums . iter (). collect :: < HashSet <& i32 >> (). len ();
let mut map = HashMap :: new ();
let mut ans = 0 ;
let mut i = 0 ;
for j in 0 .. n {
* map . entry ( nums [ j ]). or_insert ( 0 ) += 1 ;
while map . len () == m {
ans += n - j ;
let v = map . entry ( nums [ i ]). or_default ();
* v -= 1 ;
if * v == 0 {
map . remove ( & nums [ i ]);
}
i += 1 ;
}
}
ans as i32
}
}
GitHub