0494.目标和.md

解题关键点

• 第一反应是动态规划，不过因为 nums 比较小（1~20），还是先试了试暴力求解
  • 利用 HashMap 存储当前所有的计算结果，使用当前值和所有计算结果进行运算，再存储到新的 HashMap
    • 时间复杂度 O(n^2) 空间复杂度 O(n^2)。（这个解法的时间复杂度和动态规划很接近）
  • 试了一下 DFS 回溯，时间复杂度 O(2^n) 空间复杂度 O(1)，居然没有 TLE
• 动态规划
  • 首先获取所有数值之和 sum，如果 sum 小于 target 或者和 target 的奇偶性不同，就直接返回 0
  • 动态规划的目标是，找到和等于 (sum - target) 的子集数量
  • 时间复杂度 O(n * (sum - target)) 空间复杂度 O(sum - target) 不出所料的击败了 100% 的人

代码

HashMap：

impl Solution {
    pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
        use std::collections::HashMap;
        let mut map:HashMap<i32, i32> = HashMap::new();
        map.insert(nums[0], 1);
        // entry(key) 返回一个 Entry 对象
        // and_modify() 如果 Entry 存在值，则执行闭包。由于会返回当前 Entry 实例，因此可以和 or_insert 链式执行
        // or_insert() 如果 Entry 不存在值，则插入新的值，同时返回当前值的可变引用
        map.entry(-nums[0]).and_modify(|e| *e += 1).or_insert(1);
        for n in &nums[1..] {
            let mut newmap:HashMap<i32, i32> = HashMap::new();
            // 不断对计算结果进行累加
            for (k, v) in map.iter() {
                newmap.entry(k + *n).and_modify(|e| *e += v).or_insert(*v);
                newmap.entry(k - *n).and_modify(|e| *e += v).or_insert(*v);
            }
            map = newmap;
        }
        // 最后返回 target 位置的值，如果不存在，返回 0
        *map.entry(target).or_insert(0)
    }
}

DFS（利用 DP 的思路，求和用于剪枝）：

fn sum_recursion(nums: &Vec<i32>, target: i32, sum: i32, i: usize, mut res: i32, sumrest: i32) -> i32 {
    if i == nums.len() {
        if sum == target {
            res += 1;
        }
    } else {
        // sum + sumrest - nums[i] * 2 必须大于等于 target，否则就不必计算减去 nums[i] 的情况了
        res += sum_recursion(&nums, target, sum + nums[i], i + 1, *&res, sumrest - nums[i]) + if sum + sumrest - nums[i] * 2 >= target {
            sum_recursion(&nums, target, sum - nums[i], i + 1, *&res, sumrest - nums[i])
        } else {
            0
        }
    }
    res
}

impl Solution {
    pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
        // 前边这段借鉴了动态规划的方案
        let mut sum = 0;
        for n in &nums {
            sum += n;
        }
        if sum < target || (sum - target) % 2 != 0 {
            return 0;
        }
        sum_recursion(&nums, target, 0, 0, 0, sum)
    }
}

动态规划

impl Solution {
    pub fn find_target_sum_ways(nums: Vec<i32>, target: i32) -> i32 {
        // 先求和
        let mut sum = 0;
        for n in &nums {
            sum += n;
        }
        let diff = sum - target;
        // 忽略掉和比目标值小，或者奇偶性不同的情况
        if diff < 0 || diff % 2 != 0 {
            return 0;
        }
        let neg = diff / 2;
        // 创建一个 neg + 1 的向量，并填充 0
        let mut dp = vec![0; neg as usize + 1];
        // 和为 0 的情况至少 1 种
        dp[0] = 1;
        for n in nums {
            // 注意反转，否则会造成额外计算，只遍历 0 到 neg - n，忽略掉 i + n > neg 的情况
            for i in (0..=neg - n).rev() {
                dp[(i + n) as usize] += dp[i as usize];
            }
        }
        dp[neg as usize]
    }
}

测试用例

assert_eq!(find_target_sum_ways(vec![0], 0), 2);
assert_eq!(find_target_sum_ways(vec![0], 2), 0);
assert_eq!(find_target_sum_ways(vec![1, 1, 1, 1, 1], 3), 5);
assert_eq!(find_target_sum_ways(vec![0, 1, 1, 2, 2], 0), 8);
assert_eq!(find_target_sum_ways(vec![0, 1, 1, 2, 2, 0, 1, 1, 2, 2, 0, 1, 1, 2, 2, 0, 1, 1, 2, 2], 0), 129472);