2017年6月15日 星期四

[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++

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;
}
};
Java

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
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
}
}

沒有留言:

張貼留言