Description
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].
my program
思路：创建一个数组tmp，用来储存前n项的和。
第一层循环：用来计算每一个前i项的和，判断如果前i项和等于k，则结果res加一；
内层循环：遍历tmp的前i项，判断如果（前i项和-前j项和）== k，则结果res加一；
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
vector<int> tmp = nums;
int res = 0;
if (nums[0] == k) res=1;
for (int i = 1; i<nums.size(); i++) {
tmp[i] += tmp[i-1];
if (tmp[i] == k) res++;
for (int j = 0; j < i; j++) {
if (tmp[i] - tmp[j] == k) res++;
}
}
return res;
}
};Submission Details
80 / 80 test cases passed.
Status: Accepted
Runtime: 369 ms
虽然AC了，但是runtime很高，于是思考是否有更有的算法。
暴力解法
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int res = 0, n = nums.size();
for (int i = 0; i < n; ++i) {
int sum = nums[i];
if (sum == k) ++res;
for (int j = i + 1; j < n; ++j) {
sum += nums[j];
if (sum == k) ++res;
}
}
return res;
}
};Submission Details
80 / 80 test cases passed.
Status: Accepted
Runtime: 538 ms
两种解法的时间复杂度均为O(n2),类似
哈希表解法
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int res = 0;
map<int, int> tmp{{0,1}};
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
res += tmp[sum - k];
++tmp[sum];
}
return res;
}
};非常巧妙，时间复杂度仅为O(n),相当于仅仅遍历了数组。