437.path-sum-iii(普通的双重递归，高级解法先放着

问题：

1.相似的题目一起做啊
2.看隐藏提示
3.多用用几种方法啊

正文：

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        // 什么意思啊
        // 前序遍历，深度优先
        // 进行遍历全部节点
        return numberOfPaths(root, sum) + 
               pathSum(root->left, sum) + 
               pathSum(root->right, sum);
            
    }
private:
    // 统计某一节点开始的路径个数
    int numberOfPaths(TreeNode* root, int& sum){
        if (!root) return 0;
        int newsum  = sum - root->val;
        return (newsum == 0 ? 1 : 0) + 
        numberOfPaths(root->left, newsum) + 
        numberOfPaths(root->right, newsum);
    }
};

560.subarray-sum-equals-k（超时！！！！）

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if(!nums.size()) return 0;
        return subarraySum(nums, 0, k);
    }
private:
    int subarraySum(vector<int>& nums,int i, int sum){
        if(!nums.size() || i >= nums.size()) return 0;
        return numOfPaths(nums, i, sum) + subarraySum(nums, i+1,sum);;
    }

    int numOfPaths(vector<int>& nums, int i, int sum){
        if(!nums.size()||i >= nums.size()) return 0;
        int new_sum = sum - nums[i];
        return (new_sum == 0 ? 1 : 0) + numOfPaths(nums, i+1, new_sum); 
    }    
};

437的神奇解法，好难。先放着。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        if(nums.empty()) return 0;
        
        // 为什么要这么初始化呢？
        // [1,1,1] 2  
        unordered_map<int, int> counts{{0, 1}};
        
        int cur_sum = 0;
        int ans = 0;
        
        for(const int num : nums){
            cur_sum += num;

            // 对s[j] - s[i] == k 出现的个数进行计数 转换为对s[j]-k 的个数进行计数。
            ans += counts[cur_sum - k];
            // 把这个放在前面和后面又什么影响呢？ [1] 0 会是错的。
            ++counts[cur_sum];
            
        }
        return ans;
    }
};