[Array] 560Subarray sum Equal k

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

Solution

方法1：暴力解法

for (int i=0;i<size;++i){ sum = 0; for(int j=i;j<size;++j){ sum+=nums[j]; if (sum==k) count ++; } }

方法2：考虑从第0位到第k位的总和为sum[k], 如果有sum[i]-sum[j] == k，那么从i+1到j位即为符合要求到子序列。

class Solution { public: int subarraySum(vector<int>& nums, int k) { int size = nums.size(); if (size==0) return 0; int sum=0, count=0; map<int, int> map1; map1.insert(pair<int, int>(0, 1)); for(int i=0;i<size;i++){ sum += nums[i]; auto iter = map1.find(sum-k); if (iter != map1.end()){ count += map1[sum-k]; } auto iter1 = map1.find(sum); if (iter1 != map1.end()){ map1[sum] ++ ; } else{ map1[sum] = 1; } } return count; } };