最近刷題倒是沒停，但是感覺大部分遇到的不是很適合拿來水博客，畢竟方法套路比較相似，年兄推薦下做了兩道前綴和的題，感覺這類題型的思路很棒，也可以歸納成一個方法，故再來水一篇，題目均來自力扣Leetcode，傳送門，
簡單來說，前綴和適合于解決 連續，求和 相關的問題，遇到的問題如果包含相關要求，可以考慮嘗試一下前綴和的解法，諸如子陣列的哈，連續幾個數字的和，等等，
974. 和可被 K 整除的子陣列
示例：
輸入：A = [4,5,0,-2,-3,1], K = 5
輸出：7
解釋：
有 7 個子陣列滿足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
提示：
1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000
如題目描述，根據給定的陣列我們需要尋找到它的子陣列滿足條件 ==》子陣列所有數字的和可以被K整除，注意這里有個隱含條件，子陣列的每一項的索引是連續的，
假設一組陣列每一項的值都和它的下標相同:
-
- Sumx = 1 + 2 + 3 + ... + x
- Sumy = 1 + 2 + 3 + ... + y
這里不妨假設y>x, 那么 Sumy - Sumx = (x+1) + (x+2) + ... y ，這里Sumy - Sumx 就是陣列從x到y的和，我們要尋找的就是 (Sumy - Sumx ) % K = 0的子陣列，因此可以轉化為Sumy % K == Sumx % K的前綴和表達，而前綴和其實我們是可以通過一次遍歷就獲得的，只需要一個變數輔助記錄上一個位置的前綴和即可，
現在我們的題目轉化為了求得Sumy % K == Sumx % K的子陣列的個數，并且也知道了怎么計算前綴和，現在只需要使用Hash表來記錄前綴和出現的次數即可，當hash表中出現了Key相同的元素，說明我們遇到了前綴和相同，即符合條件的子陣列，注意這里同時也要更新一下Hash表中的資料，
注意對于這道題來說，負數需要特別處理一下，來看看代碼吧：
1 public class Solution { 2 public int SubarraysDivByK(int[] A, int K) 3 { 4 int result = 0; 5 List<int> preSum = new List<int>(); 6 preSum.Add(0); 7 8 Dictionary<int, int> dict = new Dictionary<int, int>(); 9 dict.Add(0, 1); 10 11 for (int i = 0; i < A.Length; i++) 12 { 13 preSum.Add(preSum[i] + A[i]); 14 int temp = preSum[i + 1] % K; 15 temp = temp < 0 ? temp + K : temp; 16 17 if (dict.Keys.Contains(temp)) 18 { 19 result += dict[temp]; 20 dict[temp] = dict[temp] + 1; 21 } 22 else 23 { 24 dict.Add(temp, 1); 25 } 26 27 } 28 29 return result; 30 } 31 }
第15行，處理一下負數的情況，將其轉為對應的%操作取得的正整數，
560. 和為K的子陣列
給定一個整數陣列和一個整數 k，你需要找到該陣列中和為 k 的連續的子陣列的個數，
示例 1 :
輸入:nums = [1,1,1], k = 2
輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況，
說明 :
陣列的長度為 [1, 20,000]，
陣列中元素的范圍是 [-1000, 1000] ，且整數 k 的范圍是 [-1e7, 1e7]，
這道題目的思路也是一樣，但我還是把它記錄了下來，因為覺得對比自己的思路和官方思路的程序很有意思， 解法和前面類似，我們也需要利用前綴和來求解，只不過這類是Sumy - Sumx = K，先來看看筆者沒有通過的的提交吧:
1 public class Solution { 2 public int SubarraySum(int[] nums, int k) 3 { 4 Dictionary<int, int> dict = new Dictionary<int, int>(); 5 6 int sum = 0; 7 8 for (int i = 0; i < nums.Length; i++) 9 { 10 sum += nums[i]; 11 int count = 0; 12 dict.TryGetValue(sum, out count); 13 dict[sum] = ++count; 14 } 15 16 int result = 0; 17 18 foreach (var item in dict) 19 { 20 if (item.Key == k) 21 { 22 result += item.Value; 23 } 24 25 int temp = item.Key + k; 26 27 if (dict.Keys.Contains(temp)) 28 { 29 if (temp != item.Key) 30 { 31 result += item.Value * dict[temp]; 32 } 33 else 34 { 35 result += (dict[temp] - 1) * (dict[temp] - 1); 36 } 37 38 } 39 40 } 41 42 return result; 43 } 44 }
上面的代碼其實已經通過了大多數的測驗用例，但在第56個用例失敗了，
case 56很簡單，輸入是[-1,-1,1] ，1，如果按照我的思路，那么儲存前綴和的Dict中的結果應該是（-1，2），（-2，1），即前綴和是-1的情況出現了兩次，前綴和是-2的情況出現了一次，此時我們要求的結果K=1, 因此對于前綴和是-2的這種情況，如果我們可以找到前綴和是-1的前綴是不是就滿足了呢？我一開始是這么想的，然鵝被現實打臉 (￣ε(#￣) 了，其實題目中滿足要求的只有[1] 這種情況，
再仔細思考，其實我遇到的問題是既需要利用Hash來實作O(1)的訪問，又需要知道順序，來過濾到不可能的情況，
再來看看官方的解法吧：
1 public class Solution { 2 public int SubarraySum(int[] nums, int k) 3 { 4 Dictionary<int, int> dict = new Dictionary<int, int>(); 5 6 int sum = 0; 7 int result = 0; 8 9 for (int i = 0; i < nums.Length; i++) 10 { 11 sum += nums[i]; 12 13 int cha = sum - k; 14 15 if (cha == 0) 16 result++; 17 18 if (dict.Keys.Contains(cha)) 19 result += dict[cha]; 20 21 int count = 0; 22 dict.TryGetValue(sum, out count); 23 dict[sum] = ++count; 24 } 25 26 return result; 27 } 28 }
還是想法不夠成熟，人家直接放到一次回圈里搞定了，邊生成Hash集合，邊處理資料，同時也避免了上面提到的那種情況，試著解釋一下上面那種情況：其實是用已生成的前綴和去減去未生成的前綴和，真實情況下這是不合邏輯的，但是由于先獨立的計算了一遍前綴和掩蓋了這個問題，
PS: 即使我一開始的思路沒錯，時間復雜度也是O(2n), 雖然最終可以計算為O(n)，而官方的直接就是O(n)，當資料量不大時，由于常數被官方完爆，ORZ
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/20454.html
標籤：C#
上一篇：急！ vb.net如何遍歷檔案夾及子檔案夾和檔案，逐一遞回？
下一篇：C#基礎篇——委托