描述
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:
1 | Input:nums = [1,1,1], k = 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].
分析
题目要求是从一个数组中,求连续子序列和为 k 的个数。数据量不是很大,可以用暴力枚举的方式,还有一种方式是使用哈希表辅助的方式,定义 sum[i] 为 0-i 的和,哈希表存的是 sum 以及和为 sum 的子序列的个数,只需要遍历一次序列,遍历的过程中求 sum,同时根据当前的 sum 求哈希表中 sum-k 对应的子序列的个数,将这些值加起来即可。
解决方案1(Java)
1 | class Solution { |