📝前言說明：

• 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄，按專題劃分
• 每題主要記錄：（1）本人解法 + 本人屎山代碼；（2）優質解法 + 優質代碼；（3）精益求精，更好的解法和獨特的思想（如果有的話）
• 文章中的理解僅為個人理解。如有錯誤，感謝糾錯

🎬個人簡介：努力學習ing
📋本專欄：C++刷題專欄
📋其他專欄：C語言入門基礎，python入門基礎，C++學習筆記，Linux
🎀CSDN主頁 愚潤澤

---

974. 和可被 K 整除的子數組

題目鏈接：974. 和可被 K 整除的子數組

個人解

思路：
和上篇文章的第三題一樣，但是，因為哈希表里面可能有多個前綴和都滿足要求，而我沒想到如何快速搜索到這些前綴和。
暴力解法：O($n^2$)是過不了的。

---

優質解

思路：

• 哈希表里面有多個前綴和滿足要求是因為：可能出現dp[x2] = dp[x1] + k的情況（即兩數之間差nk），導致對于dp[i]，可能有多個前綴和與之匹配。那如何保證唯一且能把這些數全部統計到呢？
• 我們可以在記錄前綴和的時候，不記錄前綴和，而是記錄前綴和 % k的余數。
• 因為：如果(dp[i] - dp[x]) % k == 0，則dp[i] % k == dp[x] % k
• 細節問題：我們的數組中有負數，但是C++ 中的取模性質：負數 % 正數 == 負數。所以我們要對模出來的結果進行修正
• 修正：對于負數結果修正：余數 = dp[i] % k + k，但是為了正負數同一：余數 = (dp[i] % k + k) % k

代碼：

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int, int> hash;int ans = 0, sum = 0;hash[0] = 1;for(auto x: nums){sum += x; // sum代表當前位置的前綴和int modulus = (sum % k + k) % k;if(hash.count(modulus)) ans += hash[modulus];hash[modulus]++;}return ans;}
};

時間復雜度：O($n$)
空間復雜度：O($n$)

---

525. 連續數組

題目鏈接：525. 連續數組

個人解

思路：
腦子銹了，只能想到O($n^2$)的解法。

---

優質解

思路：

• 把 0 變-1
• 問題變成：找子數組所有元素和為0的最長子數組。
• 細節1：哈希表存儲什么？ 答：<前綴和，下標>，并且如果遇到相同的前綴和，下標大的不存（因為子數組短）
• 細節2：當前位置的信息使用完以后才存入哈希表，不然dp[i] - dp[i]這個子數組實際為空
• 細節3：默認前綴和0的位置要存在-1

代碼：

class Solution {
public:int findMaxLength(vector<int>& nums) {int ans = 0, sum = 0;unordered_map<int, int> hash;hash[0] = -1;for(int i = 0; i < nums.size(); i++){sum += (nums[i] == 0? -1 : 1);if(hash.count(sum)) ans = max(ans, i - hash[sum]);elsehash[sum] = i;}return ans;}
};

時間復雜度：O(n)
空間復雜度：O(n)

---

1314. 矩陣區域和

題目鏈接：1314. 矩陣區域和

個人解

這道題和文章中第二題很像，這道題麻煩在下標對應。
思路：

• 題意：answer中每一格表示的是：以mat[r][c]為中心的，邊長為2k+1的正方形中所有元素（且在mat中）的和
• 建立一個二維前綴和數組：dp[i][j]代表mat 的 [0, 0]到[i, j]這個矩陣內的元素和
• 然后利用這個前綴和數組來填寫answer
• 下標對應：初始化時：因為mat的元素是從下標[0, 0]開始的，所以dp[i][j]加的應該是mat[i - 1][j - 1]
• 使用時：dp[1][1]才對應mat的第一個元素，所以，在使用dp的時候下標都要-1

用時：20:00
屎山代碼：

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size(), n = mat[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));vector<vector<int>> answer(m, vector<int>(n, 0));// 初始化前綴和數組for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++)dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){int x1 = max(0, i - k);int y1 = max(0, j - k);int x2 = min(m - 1, i + k);int y2 = min(n - 1, j + k);answer[i][j] = dp[x2 + 1][y2 + 1] - dp[x1][y2 + 1] - dp[x2 + 1][y1] + dp[x1][y1];}}return answer;}
};

時間復雜度：O($m?n$)
空間復雜度：O($m?n$)

---

🌈我的分享也就到此結束啦🌈
要是我的分享也能對你的學習起到幫助，那簡直是太酷啦！
若有不足，還請大家多多指正，我們一起學習交流！
📢公主，王子：點贊👍→收藏?→關注🔍
感謝大家的觀看和支持！祝大家都能得償所愿，天天開心！！！