暴力解法:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = i; j < n; ++j) {
sum += nums[j];
if (sum == k) {
count++;
}
}
}
return count;
}
前缀和+哈希表,O(N)时间复杂度解法,
int subarraySum(vector<int> &nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0, pre = 0;
for (auto &x : nums) {
pre += x;
if (mp.find(pre - k) != mp.end()) {
count += mp[pre - k];
}
mp[pre]++;
}
return count;
}
参考题目:
https://leetcode.cn/problems/subarray-sum-equals-k/
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)