Re: [閒聊] 每日leetcode已回收
這題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
推
03/30 13:41,
1年前
, 1F
03/30 13:41, 1F
→
03/30 14:07,
1年前
, 2F
03/30 14:07, 2F
→
03/30 20:21,
1年前
, 3F
03/30 20:21, 3F
→
03/30 20:27,
1年前
, 4F
03/30 20:27, 4F
→
03/30 20:39,
1年前
, 5F
03/30 20:39, 5F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 79 之 1548 篇)：