437. Path Sum III
题目：
找一棵树上连续节点和等于 target 的数量
思路：
这题如果用暴力 dfs 遍历
写很快 但很慢 会变成 O(n^2)
可以用类似储存状态的方式
前缀和 + HashMap
就是你每次储存前面节点的和
root, root+node1, root+node1+node2 这样累积路径和
那你用传承下来的 curr_sum 去减这些节点
然后放进纪录的 HashMap 找
就能直接获得是否有符合答案的组合
记得要先更新 curr_sum 放进 HashMap 再跑下面节点
最后回来的时候会一层一层 把用过的节点扣掉 变成0就删除
因为用 HashMap 是每个节点共同维护表 避免污染
还有中间要转 i64 计算
因为 i32 会在最后一个测资大爆炸==
Code:
use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;
impl Solution {
pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32)-> i32
{
fn dfs(
node: Option<Rc<RefCell<TreeNode>>>,
curr_sum: i64,
target: i32,
prefix: &mut HashMap<i64, i64>,
) -> i64 {
match node {
Some(rc_node) => {
let node = rc_node.borrow();
let curr_sum = curr_sum as i64 + node.val as i64;
let mut count = *prefix.get(&(curr_sum - target as i64))
.unwrap_or(&0);
*prefix.entry(curr_sum).or_insert(0) += 1;
count += dfs(node.left.clone(), curr_sum, target, prefix);
count += dfs(node.right.clone(), curr_sum, target, prefix);
let entry = prefix.get_mut(&curr_sum).unwrap();
*entry -= 1;
if *entry == 0 {
prefix.remove(&curr_sum);
}
count
}
None => 0,
}
}
let mut prefix = HashMap::new();
prefix.insert(0, 1);
dfs(root, 0, target_sum, &mut prefix) as i32
}
}

别卷了