🔗 🟡 3185. Count Pairs That Form a Complete Day II 1385

tags: `Weekly Contest 402` `雜湊表(Hash Table)` `模運算(Modulo)`

題意

給定一個整數陣列 $\text{hours}$ 。返回有多少對 $(i, j)$ 滿足 $i < j$ 且 $\text{hours}[i] + \text{hours}[j]$ 為 $24$ 的整數倍數。

約束條件

$1 \leq n = \text{hours.length} \leq 5 \cdot 10^5$
$1 \leq \text{hours}[i] \leq 10^9$

思路：雜湊表(Hash Table) + 模運算(Modulo)

從 3184. Count Pairs That Form a Complete Day I _{[🔗解題紀錄]} 的暴力法中可以注意到，我們在考慮到 $nums[i]$ 時，只需要知道左側的數字中有多少個數字 $y$ 滿足 $y + nums[i] \equiv 0 \pmod{24}$ 。這樣我們就可以在 $\mathcal{O}(1)$ 的時間內計算出答案。

因此可以使用類似於 1. Two Sum 的方法，使用雜湊表(Hash Table) 來記錄每個數字的出現次數，然後對於每個數字 $x$ ，我們只需要查詢 $24 - (x \bmod{24})$ 的出現次數即可。

但需要注意到存在一種特殊情況，即 $x = 0$ 的情況，此時 $24 - x = 24$ ，可以使用特判或二次取模的方式來處理。

具體步驟如下：

建立一個大小為 $24$ 的陣列 $\text{cnt}$ 來記錄每個數字對 $24$ 取模後的出現次數。
遍歷 $\text{hours}$ $hours$ 陣列，對於每個元素 $x$ $x$ ：
- 計算 $x \bmod{24}$ (也就是小時數對 $24$ 取餘)
- 如果 $x$ 不為 $0$ ，則將 $\text{cnt}[24 - x]$ 加到答案 $\text{ans}$ 上(因為 $\text{hours}[i] + \text{hours}[j] = 24$ 時， $i$ 和 $j$ 就是一對)；如果 $x$ 為 $0$ ，則將 $\text{cnt}[0]$ 加到答案 $\text{ans}$ 上。
- 或是做二次取模，將 $\text{cnt}[(24 - x) \bmod{24}]$ 加到答案 $\text{ans}$ 上。
- 將 $\text{cnt}[x]$ 加 $1$ ，更新計數。
最後返回答案 $\text{ans}$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 為陣列的長度。
空間複雜度： $\mathcal{O}(24) = \mathcal{O}(1)$ 。

class Solution:
    def countCompleteDayPairs(self, hours: List[int]) -> int:
        ans = 0
        cnt = [0] * 24
        for x in hours:
            x %= 24
            # ans += cnt[24 - x] if x != 0 else cnt[0] # 特判
            ans += cnt[(24 - x) % 24] # 二次取模
            cnt[x] += 1
        return ans

class Solution {
public:
    long long countCompleteDayPairs(vector<int>& hours) {
        long long ans = 0;
        vector<int> cnt(24, 0);
        for (int x : hours) {
            x %= 24;
            // ans += (x != 0) ? cnt[24 - x] : cnt[0]; 
            ans += cnt[(24 - x) % 24];
            cnt[x]++;
        }
        return ans;
    }
};

寫在最後

PROMPT

Mystical Moonlight Encounter: A young anime girl, dressed in a black cape and witch hat, holds a pumpkin with an intense gaze. Standing before a large window framing a moonlit night sky, her focus is riveted on the pumpkin. To her left, a vibrant yellow pumpkin sits atop a straw bale amidst autumn leaves, adding a burst of warmth to the enchanting scene.