[LeetCode] 560. Subarray Sum Equals K

轉自LeetCode

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

<Solution>

這題可以用 HashMap 來思考，思路如下

• 歷遍 nums，並且計算總和

• 到 HashMap 查看 sum - k 是否有值。如果有值，就代表至少有一個 subarray 的總和等於 sum - k，將其值算到最終答案

• HashMap 的初始值為 table[0] = 1。這是因為當 sum = k 時，table[0] 必須要有一個值，不然最終答案會錯

• 將當下的總和 sum 記錄到 HashMap

code 如下(參考資料)

C++

Java


Kotlin