838. Subarray Sum Equals K

int subarraySumEqualsK(vector<int> &nums, int k) { // write your code here int n = nums.size(); if(n == 0){ return 0; } vector<int> prefixSum(n + 1, 0); int sum = 0; for(int i = 0; i < n; i++){ sum += nums[i]; prefixSum[i + 1] = sum; } int res = 0; for(int i = 0; i < n + 1; i++){ for(int j = i + 1; j < n + 1; j++){ if(prefixSum[j] - prefixSum[i] == k){ res++; } } } return res; }
超时

过了，但脑子锈掉了，写出这么冗长的代码
int subarraySumEqualsK(vector<int> &nums, int k) { // write your code here int n = nums.size(); if(n == 0){ return 0; } vector<int> prefixSum(n + 1, 0); unordered_map<int, vector<int>> m; int sum = 0; m[0].push_back(0); for(int i = 0; i < n; i++){ sum += nums[i]; m[sum].push_back(i + 1); prefixSum[i + 1] = sum; } // brute force int res = 0; for(int i = 0; i < n + 1; i++){ if(m.find(prefixSum[i] + k) != m.end()){ vector<int> arr = m[prefixSum[i] + k]; for(int j = 0; j < arr.size(); j++){ if(i < arr[j]){ res++; } } } } return res; }
正确的方式，我觉得脑子清醒的情况下，一下写出这个代码不难。醒一醒！！
int subarraySumEqualsK(vector<int> &nums, int k) { // write your code here int n = nums.size(); if(n == 0){ return 0; } //vector<int> prefixSum(n + 1, 0); unordered_map<int, int> m; int sum = 0; int res = 0; m[0]++; for(int i = 0; i < n; i++){ sum += nums[i]; if(m.find(sum - k) != m.end()){ res += m[sum - k]; } m[sum]++; } // hash map return res; }