推 wwndbk: 大師 03/30 13:41
→ SecondRun: 大師 03/30 14:07
→ Rushia: 剩我解不出來了 03/30 20:21
→ Rushia: n^2 居然可以過 03/30 20:27
→ Rushia: 好像過不了欸 [1,2,1,2,...] 20000個就TLE了 但他測資沒有 03/30 20:39
這題acceptance rate有57%應該算是hard裡面比較簡單的
992. Subarrays with K Different Integers
有一個array nums、整數 k
定義good subarrays:
當一個subarray裡有k種不同的整數，那這個sub array就是good subarray
思路 :
用sliding window + hash table
l:左指標代表目前subarray的起點
r:右指標代表目前subarray的終點
hash table記錄這個整數出現的次數
當該整數出現第一次counter加1
counter==k的時候
從l開始開始計算滿足條件的subarray有幾個
counter>k的時候
移動l直到counter==k
golang code :
func subarraysWithKDistinct(nums []int, k int) int {
cnt := 0
ans := 0
rec := make(map[int]int)
l, r, n := 0, 0, len(nums)
for r < n {
rec[nums[r]]++
if rec[nums[r]] == 1 {
cnt++
}
for cnt > k {
rec[nums[l]]--
if rec[nums[l]] == 0 {
cnt--
}
l++
}
temp := l
tempmap := make(map[int]int)
for temp <= r && cnt == k {
tempmap[nums[temp]]++
ans++
if tempmap[nums[temp]] == rec[nums[temp]] {
break
}
temp++
}
r++
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.141.243.109 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1711776973.A.443.html