原题链接：

思路（又是脑子短路没想到的一天）：
前缀和+hash。需要确定第i个位置之前有多少的前缀和相加为0，只需要确定前缀和中有多少个值为preSum[i] - goal。然后后半部分就是目标和了。

实现：

  1. class Solution {
  2. public:
  3.     int numSubarraysWithSum(vector<int>& nums, int goal) {
  4.         int sum = 0;
  5.         unordered_map<int, int> mp;
  6.         int ans = 0;
  7.         for(int i = 0; i < nums.size(); i++){
  8.             mp[sum]++;
  9.             sum += nums[i];
  10.             ans += mp[sum - goal];
  11.         }
  12.         return ans;
  13.     }
  14. };

相关练习题：

724. 寻找数组的中心下标

思路1：前缀和后缀和都算一次，然后直接比较。
实现：

  1. class Solution {
  2. public:
  3.     int preSum[10005], endSum[10005];
  4.     int pivotIndex(vector<int>& nums) {
  5.         int len = nums.size();
  6.         preSum[0] = nums[0], endSum[len - 1] = nums[len - 1];
  7.         for(int i = 1; i < len; i++){
  8.             preSum[i] = preSum[i - 1] + nums[i];
  9.         }
  10.         for(int j = len - 2; j >= 0; j--){
  11.             endSum[j] = endSum[j + 1] + nums[j];
  12.         }
  13.         for(int i = 0; i < len; i++){
  14.             int pre, end;
  15.             if(i >= 1 && i < len - 1)
  16.                 pre = preSum[i - 1], end = endSum[i + 1];
  17.             else if(i < 1){
  18.                 pre = 0, end = endSum[i + 1];
  19.             }else if(i >= len - 1){
  20.                 pre = preSum[i - 1], end = endSum[i + 1];
  21.             }
  22.             if(pre == end)return i;
  23.         }
  24.         return -1;
  25.     }
  26. };

思路2：计算前缀和与总和，前缀和成2加上当前位置的数值等于总和即为答案。
实现：

  1. class Solution {
  2. public:
  3.     int pivotIndex(vector<int>& nums) {
  4.         int total = accumulate(nums.begin(), nums.end(), 0);
  5.         int sum = 0;
  6.         for(int i = 0; i < nums.size(); i++){
  7.             if(sum * 2 + nums[i] == total){
  8.                 return i;
  9.             }
  10.             sum += nums[i];
  11.         }
  12.         return -1;
  13.     }
  14. };

1. 两数之和

思路：两个哈希表，一个存放出现的值，一个存放值对应的索引。
实现：

  1. class Solution {
  2. public:
  3.     vector<int> twoSum(vector<int>& nums, int target) {
  4.         map<int, int> mp;
  5.         map<int, int> mp2;
  6.         vector<int> ans(2);
  7.         for(int i = 0; i < nums.size(); i++){
  8.             int t;
  9.             if(mp[target - nums[i]] != 0){
  10.                 ans[0] = mp2[target - nums[i]], ans[1] = i;
  11.                 return ans;
  12.             }
  13.             mp[nums[i]] = 1;
  14.             mp2[nums[i]] = i;
  15.         }
  16.         return ans;
  17.     }
  18. };

其实不需要两个哈希表，直接一个哈希表存放数值对应的下标就可以了。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mp;
        vector<int> ans(2);
        for(int i = 0; i < nums.size(); i++){
            int t;
            if(mp[target - nums[i]] != 0){
                ans[0] = mp[target - nums[i]] - 1, ans[1] = i;
                return ans;
            }
            mp[nums[i]] = i + 1;
        }
        return ans;
    }
};