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:
- The length of the array is in range [1, 20,000].
- The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].
這題可以用 HashMap 來思考,思路如下
- 歷遍 nums,並且計算總和
- 到 HashMap 查看 sum - k 是否有值。如果有值,就代表至少有一個 subarray 的總和等於 sum - k,將其值算到最終答案
- HashMap 的初始值為 table[0] = 1。這是因為當 sum = k 時,table[0] 必須要有一個值,不然最終答案會錯
- 將當下的總和 sum 記錄到 HashMap
C++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
int subarraySum(vector<int>& nums, int k) { | |
int sum = 0, ans = 0; | |
unordered_map<int, int> table; | |
table[0] = 1; | |
for(int const &n : nums) { | |
sum += n; | |
//>> if table[sum - k] exists | |
//>> then there must be at least one sum of subarray equal sum-k | |
ans += table[sum - k]; | |
//>> record current sum | |
++table[sum]; | |
} | |
return ans; | |
} | |
}; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Solution { | |
public int subarraySum(int[] nums, int k) { | |
int sum = 0, ans = 0; | |
HashMap<Integer, Integer> table = new HashMap<>(); | |
table.put(0, 1); | |
for(final int n : nums) { | |
sum += n; | |
//>> if table[sum - k] exists | |
//>> then there must be at least one sum of subarray equal sum-k | |
ans += table.getOrDefault(sum-k, 0); | |
//>> record current sum | |
table.put(sum, table.getOrDefault(sum, 0) + 1); | |
} | |
return ans; | |
} | |
} |
Kotlin
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
fun subarraySum(nums: IntArray, k: Int): Int { | |
val map = mutableMapOf<Int,Int>() | |
var ans = 0 | |
var sum = 0 | |
map[0] = 1 | |
/* | |
1. Hashmap<sum[0,i - 1], frequency> | |
2. sum[i, j] = sum[0, j] - sum[0, i - 1] --> sum[0, i - 1] = sum[0, j] - sum[i, j] | |
k sum hashmap-key --> hashmap-key = sum - k | |
3. now, we have k and sum. | |
As long as we can find a sum[0, i - 1], we then get a valid subarray | |
which is as long as we have the hashmap-key, we then get a valid subarray | |
4. Why don't map.put(sum[0, i - 1], 1) every time ? | |
if all numbers are positive, this is fine | |
if there exists negative number, there could be preSum frequency > 1 | |
*/ | |
for(n in nums) { | |
sum += n | |
ans += map[sum - k]?.let { it } ?: 0 | |
map[sum] = map[sum]?.let { it + 1 } ?: 1 | |
} | |
return ans | |
} | |
} |
沒有留言:
張貼留言