560. 和为K的子数组

暴力解法

 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;

 

上一篇:消息人士:大众正调整560亿美元电动汽车电池采购方案


下一篇:560和为k的子数组