分析
-
本题的考点:前缀和、哈希表。
-
我们使用数组
s
表示nums
的前缀和,当我们考虑s[i]
时,我们希望找到存在多少个j
,使得s[i]-s[j-1]=k
,其中1<=j<=i
,相当于让我们找到存在多少个s[i]-k
,因此可以使用哈希表记录前面数据出现的次数即可。
代码
- C++
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> s(n + 1);
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + nums[i - 1];
unordered_map<int, int> hash; // (数据,出现次数)
hash[0] = 1;
int res = 0;
for (int i = 1; i <= n; i++) {
res += hash[s[i] - k];
hash[s[i]]++;
}
return res;
}
};
- Java
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length;
int[] s = new int[n + 1];
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + nums[i - 1];
HashMap<Integer, Integer> hash = new HashMap<>();
hash.put(0, 1);
int res = 0;
for (int i = 1; i <= n; i++) {
res += hash.getOrDefault(s[i] - k, 0);
hash.put(s[i], hash.getOrDefault(s[i], 0) + 1);
}
return res;
}
}
- Python
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
s = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
s[i] = s[i - 1] + nums[i - 1]
hash = {}
hash[0] = 1
res = 0
for i in range(1, n + 1):
if s[i] - k in hash:
res += hash[s[i] - k]
if s[i] in hash:
hash[s[i]] += 1
else:
hash[s[i]] = 1
return res
时空复杂度分析
-
时间复杂度:$O(n)$,
n
为数组长度。 -
空间复杂度:$O(n)$。