文章目錄

• 題目描述
• 思路 & 代碼
• • • 暴力法 O($n^2$)
    • 前綴和 + 哈希表 O(n)
    • 二刷

題目描述

• 第一道前綴和題目～
  

思路 & 代碼

暴力法 O($n^2$)

• 固定一個值，從后往前找滿足的條件即可

class Solution {public int subarraySum(int[] nums, int k) {int ans = 0;for(int i = 0; i < nums.length; i++){int temp = 0;for(int j = i; j >= 0; j--){temp += nums[j];if(temp == k){ans++;}}}return ans;} }

前綴和 + 哈希表 O(n)

• 連續子數組值 = preNum[j] - preNum[i]，很巧妙
• 一次遍歷動態哈希，一邊維護一邊找～

class Solution {public int subarraySum(int[] nums, int k) {// 前綴和 & 哈希表(前綴和值 - 出現次數)Map<Integer, Integer> hashmap = new HashMap<>();// 代表第一個元素的前綴和，初始化hashmap.put(0, 1);int preSum = 0;int ans = 0;for(int num : nums){preSum += num;// 如果之前有滿足的前綴和（注意是 preSum - k）if(hashmap.containsKey(preSum - k)){ans += hashmap.get(preSum - k);}// 維護哈希表hashmap.put(preSum, hashmap.getOrDefault(preSum, 0) + 1);}return ans;} }

二刷

• 才發現對前綴和這個概念不是很熟悉…
• 說實話我覺得這題代碼相對抽象，有必要用點簡單例子人腦走一遍：
• 比如 map.put(0, 1) 這一行（比如[1, 1], 2。沒有這一行就直接得 0 了）
• （雖然圖片有點丑，但是請勉強看看吧 = = ）
• 這么個意思，累加 sum，如果發現當前 sum，在 - k 之后的值，曾經出現過，那么說明存在圖中連續的橙色子數組，滿足累加和 = k！
  

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>();map.put(0, 1);int sum = 0, res = 0;for(int temp : nums) {sum += temp;if(map.containsKey(sum - k)) {res += map.get(sum - k);}map.put(sum, map.getOrDefault(sum, 0) + 1);}return res;} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】560. 和为K的子数组（Java、前缀和、哈希表）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。