1、題目：LCR 010. 和為 K 的子數組

• https://leetcode.cn/problems/QTMn0o/description/

給定一個整數數組和一個整數 k ，請找到該數組中和為 k 的連續子數組的個數。示例 1：
輸入:nums = [1,1,1], k = 2
輸出: 2
解釋: 此題 [1,1] 與 [1,1] 為兩種不同的情況示例 2：
輸入:nums = [1,2,3], k = 3
輸出: 2

審題：

• 輸入一個整數數組和一個整數值k，要求從整數數組中找出存在的子數組個數，要求子數組的和等于k

2、暴力解法

• 雙層for循環，外層for循環定位子數組的開始位置，內層for循環定義子數組的結束位置，
• 在內層for循環中，將子數組所有的元素相加，判斷結果累加結果sum是否等于目標值k，如果等于則找到符合要求的子數組，符合子數組個數結果值+1

代碼實現

int subarraySum(vector<int> &nums, int k)
{int res = 0;int size = nums.size();int sum = 0;for (int i = 0; i < size; i++){sum = 0;for (int j = i; j < size; j++){sum += nums[j];if (k == sum){res++;}}}return res;
}

3、數組累加法

• 將數組中所有元素的值累加起來，使用哈希表保存子數組累加和出現的次數，判斷子數組的累加和是否等于目標值k
• 中間子數組的累加和，可以通過整個范圍的子數組累加和，減去前面部分子數組的累加和。
• 例子：

有數組 {1，2，3，4，5，6} 加入要求子數組和為9的子數組出現的個數
可以通過累加計算得到前三個數組元素的累加和 S3 = 1+2+3 = 6
前5個數組元素累加和為 S5 = 1+2+3+4+5 = 15；
那子數組累加和為9的子數組 = S5 - S3；
可通過計算累加相減是否等于目標值來求符合條件的子數組

代碼實現

int subarraySum(vector<int> &nums, int k)
{int res = 0;std::map<int, int> sumCountMap;// 往map中插入元素sumCountMap[0] = 1;int sum = 0;for (int i = 0; i < nums.size(); i++){sum += nums[i];// 判斷是否存在 sum-k的key值if (sumCountMap.find(sum - k) != sumCountMap.end()){res += sumCountMap.at(sum - k);}// 在往map中插入累加值int count = 0;if (sumCountMap.find(sum) != sumCountMap.end()){count = sumCountMap.at(sum);}sumCountMap[sum] = count + 1;}return res;
}

4、總結

• 求子數組的累加和等于某個目標值，如果數組元素全是正整數，可以使用雙指針解法，但數組元素只是整數，那就會存在正整數與負整數，使用雙指針累加法就覆蓋不到所有結果。
• 暴力解法使用雙層for循環，可以檢索所有的子數組情況，但時間復雜度為n的平方
• 采用數組累加求和方式，可通過子數組累加和相減得到某段區域的子數組累加和。使用哈希表保存子數組累加和出現的次數
• map數據結構使用，使用find方法查詢key值是否存在，at方法獲取value值，還可以使用賦值語句[]獲取value值