每日算法學習記錄 - 250602

今天學習和復習了兩道利用前綴和與哈希表解決的子數組問題，特此記錄。

560. 和為 K 的子數組

題目

思路

本題的核心思想是利用 前綴和 與 哈希表 來優化查找過程。

解題過程

題目要求統計和為 k 的子數組個數。

1. 我們首先預處理出一個前綴和數組 prefix，其中 prefix[i] 表示原數組 nums 中區間 [0, i-1] 的元素之和。特別地，prefix[0] = 0。
2. 對于任意子數組 nums[i...j-1] (假設 j > i)，其和可以表示為 prefix[j] - prefix[i]。
3. 我們目標是找到滿足 prefix[j] - prefix[i] = k 的 (i, j) 對的個數。
4. 將上式變形，得到 prefix[i] = prefix[j] - k。
5. 我們可以遍歷計算出的 prefix 數組（從 prefix[0] 到 prefix[n]，其中 n 是 nums 的長度）。當遍歷到 prefix[j]（在代碼中用變量 x 表示）時，我們希望在 之前已經遇到過 的前綴和中查找是否存在一個 prefix[i]，使得 prefix[i] == prefix[j] - k。
6. 使用一個哈希表 map 來存儲已經遍歷過的前綴和 sum_val 及其出現的次數 count (即 map<sum_val, count>)。
7. 當我們遍歷 prefix 數組，對于當前的元素 x (它代表一個 prefix[j])

這樣，通過一次遍歷，我們就能統計出所有和為 k 的子數組數量。

復雜度

• 時間復雜度: $O(N)$，其中 $N$ 是數組 nums 的長度。計算前綴和數組需要 $O(N)$，遍歷前綴和數組并操作哈希表（插入和查找平均 $O(1)$）也需要 $O(N)$。
• 空間復雜度: $O(N)$，主要用于存儲前綴和數組和哈希表。在最壞情況下，哈希表可能存儲 $N+1$ 個不同的前綴和。

Code

class Solution {public int subarraySum(int[] nums, int k) {int ret = 0, n = nums.length;int[] prefix = new int[n + 1];Map<Integer, Integer> map = new HashMap<>(n + 1);for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + nums[i];}for (int x : prefix) {int key = x - k;ret += map.getOrDefault(key, 0);map.put(x, map.getOrDefault(x, 0) + 1);}return ret;}
}

930. 和相同的二元子數組（復習）

題目

說明

這道題是復習題。之前使用過滑動窗口的解法（可參考 每日算法-250404），本次采用與上一題 (560. 和為 K 的子數組) 類似的 前綴和 + 哈希表 思路。

由于解題邏輯與上一題高度一致（只是目標和從 k 變成了 goal），這里不再贅述詳細過程，僅列出代碼實現。核心都是計算前綴和，然后查找 current_prefix_sum - goal 是否在哈希表中出現過。

代碼

class Solution {public int numSubarraysWithSum(int[] nums, int goal) {int ret = 0, n = nums.length;int[] prefixSum = new int[n + 1];Map<Integer, Integer> map = new HashMap<>(n + 1);for (int i = 0; i < n; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];}for (int x : prefixSum) {int key = x - goal;ret += map.getOrDefault(key, 0);map.put(x, map.getOrDefault(x, 0) + 1);}return ret;}
}