暴力解法
1 int subarraySum(vector<int>& nums, int k) { 2 vector<int> res(nums.size()+1, 0); 3 for (int i = 1; i <= nums.size(); ++i) 4 { 5 res[i]= res[i-1] + nums[i-1]; 6 7 } 8 int count = 0; 9 for (int i = 0; i <= nums.size(); ++i) 10 { 11 for (int j =i+1;j <= nums.size(); ++j) 12 { 13 if (res[j]-res[i] == k) 14 ++count; 15 } 16 } 17 return count; 18 }
hash解法
1 int size = nums.size(); 2 if (size == 1) 3 { 4 if (nums[0] == k) 5 return 1; 6 else 7 return 0; 8 } 9 map<int, int> mp; 10 int sum = 0; 11 mp[0] = 1; 12 int count = 0; 13 int remain = 0; 14 for (int i = 0; i < nums.size(); ++i) 15 { 16 sum += nums[i]; 17 18 remain = sum - k; 19 if (mp.find(remain) != mp.end()) 20 { 21 count += mp[remain]; 22 } 23 24 if (mp.find(sum) != mp.end()) 25 { 26 mp[sum] +=1; 27 } 28 else 29 mp[sum] = 1; 30 } 31 return count;