[閒聊] 每日leetcode 75 - Day18

[yam276 (史萊哲林的優等生)]

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
    }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.248.143.163 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1750920603.A.934.html
※ 編輯: yam276 (60.248.143.163 臺灣), 06/26/2025 14:50:19
推 DJYOSHITAKA: 別卷了