前缀和+哈希map优化

[剑指offer专项突击第十题](剑指 Offer II 010. 和为 k 的子数组 - 力扣（Leetcode）)

和为k的子数组

题意：

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

示例 1：

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

示例 2：

输入:nums = [1,2,3], k = 3
输出: 2

分析：

很容易想到暴力解法：遍历所有子数组（时间复杂度为O(n * n)）并计算每个子数组的和(时间复杂度为O(n)),可见暴力解法的时间复杂度为O(n * n * n)

如何用空间换时间改进暴力解法呢：

​ 可以引入哈希表，先遍历一遍数组，将从数组第一个元素累加到当前元素之和(记为变量sum)存到键(key)中，值(value)为累加和sum出现的次数。假设数组前i个数字之和为x，若存在数组的前j（0<j<i）个数字之和为x-k，则数组[j,i]就是我们要找的目标子数组。

​ 设置sum、count和hashmap三个变量。从头遍历一次数组，对数组中的每个元素执行以下操作：

1. 更新累计值sum
2. 查找哈希表中是否存在sum - k的键
3. hashmap[sum - k]记录了满足条件子数组的数量，将值添加到count上（c++中哈希表默认值为0）
4. 更新哈希表，hashmap[sum]++

​ 注意哈希表创建时要设置map[0] = 1，如果有一个从数组第一个元素开始组成的子数组前缀和正好是第一个等于k 的情况， 不加map[0] = 1,就会遗漏+1 的操作。

前缀和+哈希map优化解法的时间复杂度为O(n)!!!

代码：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hashmap;
        hashmap.insert({ 0, 1 });
        int sum = 0;
        int count = 0;
        for (auto &x:nums) {
            sum += x;
            if (hashmap.find(sum - k) != hashmap.end()) {
                //hashmap.end()指向unordered_map容器中容器中最后一个元素之后的位置
                count += hashmap[sum - k];
            }
            hashmap[sum]++;//构建哈希表
        }
        return count;
    }
};

向下的路径节点之和

剑指 Offer II 050. 向下的路径节点之和 - 力扣（Leetcode）

题意：

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

分析：

可以使用暴力解，遍历所有可能存在的路径,首先从根节点遍历所有节点(O(n))，对于每个节点寻找以该节点为根节点的所有路径,对每一个路径求和并判断是否等于targetSum(时间复杂度为O(n)) 共计时间复杂度是n的平方级。

也可以使用前缀和+哈希map优化：

1. 更新当前的 sum 值
2. 从哈希表中找到当前路径符合要求的个数并累加到全局变量res上 res += mp[k];
3. 将当前的路径和存入哈希表 mp[sum]++;
4. 调用递归函数计算左右子树的符合要求的路径数
5. 离开当前字节点时更新哈希表去除记录当前的 sum(当前子节点已经不在访问路径中了) mp[sum]–;

需要注意的是新增的第127个测试用例数组过大，应使用long long类型数据

代码：

暴力解法:

class Solution {
public:
    int pathSum(TreeNode* root, long long targetSum) {
        if(root==nullptr){
            return 0;
        }
        int result=0;
        //对于二叉树的每个节点，都执行一次dfs函数
        result+=dfs(root,targetSum);
        //遍历二叉树的每个节点
        result+=pathSum(root->left,targetSum);
        result+=pathSum(root->right,targetSum);
        return result;
    }
private:
    //遍历从某节点出发的所有路径
    int dfs(TreeNode* node,long long targetSum){
        if(node==nullptr){
            return 0;
        }
        int result=0;
        if(targetSum==node->val){
            result++;
        }
        result+=dfs(node->left,targetSum-node->val);
        result+=dfs(node->right,targetSum-node->val);
        return result;
    }
};

优化解法：

class Solution {
private:
    unordered_map<long long, int> r = {{0,1}};
    int res = 0;

public:
    int pathSum(TreeNode* root, int targetSum) {
        long long _sum = 0;
        _dfs(root, _sum, targetSum);
        return res;
    }

    void _dfs(TreeNode* root, long long cur_sum, int targetSum) {
        if (!root) return;
        cur_sum += root->val;
        if (r.find(cur_sum - targetSum) != r.end()) res += r[cur_sum - targetSum];
        ++r[cur_sum];
        _dfs(root->left, cur_sum, targetSum);
        _dfs(root->right, cur_sum, targetSum);
        --r[cur_sum];
    }
};