※ 引述《oin1104 (是oin的說)》之銘言： : 題目 : 請問有多少個子字串裡面有至少k對相同的數字 : 思路1 : 我的好像有點怪 不過很酷 : 先算出總共有幾個子字串 : 用sliding window 找到小於k對的子字串 : 然後慢慢減掉就好了 : 姆咪 : 思路2 (一般的) : 只要sliding window + hash map記錄就好 : 確保windows 裡面有剛好k組的話 : 要+的數量就是每次的l : 反正裡面的k一定會比較多 : 姆咪 睡覺前寫一下 所以java的Map怎麼那麼大便 我糙你馬 Java Code: ---------------------------------------------- class Solution { public long countGood(int[] nums, int k) { long res = 0; int l = 0; int pairs = 0; Map<Integer, Integer> countMap = new HashMap<>(); for (int r = 0; r < nums.length; r++) { countMap.put(nums[r], countMap.getOrDefault(nums[r], 0) + 1); pairs += countMap.get(nums[r]) - 1; while (pairs >= k) { int nextCount = countMap.get(nums[l]) - 1; countMap.put(nums[l], nextCount); pairs -= nextCount; l++; } res += l; } return res; } } ---------------------------------------------- -- https://i.imgur.com/pD41PYS.jpeg -- ※ 發信站: 批踢踢實業坊(pttbestweb.org.tw), 來自: 49.159.104.111 (臺灣) ※ 文章網址: https://pttbestweb.org.tw/Marginalman/M.1744824976.A.CED