LeetCode 494 Target Sum：两种字典判断方式致TLE差异的原因

核心问题：逻辑错误引发的重复计算 #

你遇到的超时问题，本质不是dp.get((i,t))和(i,t) in dp的性能差异，而是用get判断存在性时的逻辑漏洞：

• 在Target Sum的递归场景中，某些状态(i,t)对应的结果可能是0（比如当前路径无法凑出目标和）。
• 如果你写的是if dp.get((i,t)):，Python会把0当成布尔值False，误以为这个状态没被计算过，从而重复执行递归逻辑，导致指数级的冗余计算，直接触发超时。
• 而(i,t) in dp只检查字典中是否存在这个键，完全不关心对应的值是什么，不管值是0还是其他数字，都能正确命中已计算的状态，避免重复递归。

两种写法的底层处理差异 #

从Python字典的实现角度，两者确实有细微的执行区别：

• 两者都会先计算键(i,t)的哈希值，定位到对应的哈希桶。
• (i,t) in dp：遍历桶内条目对比键是否相等，找到就返回True，全程不涉及值的读取或返回，操作更轻量。
• dp.get((i,t))：找到匹配的键后，还要取出对应的值返回；如果没找到，还要生成默认的None值返回。这部分额外开销极小，但在上述逻辑错误导致的重复计算面前，这点差异完全可以忽略——真正的元凶是重复递归。

错误与正确代码示例对比 #

超时的错误写法（逻辑漏洞）

dp = {}
def dfs(i, target):
    if i == len(nums):
        return 1 if target == 0 else 0
    # 当dp[(i,target)]为0时，这个判断会返回False，触发重复计算
    if dp.get((i, target)):
        return dp[(i, target)]
    add = dfs(i+1, target + nums[i])
    sub = dfs(i+1, target - nums[i])
    dp[(i, target)] = add + sub
    return dp[(i, target)]

正常运行的正确写法

dp = {}
def dfs(i, target):
    if i == len(nums):
        return 1 if target == 0 else 0
    # 只检查键是否存在，不受值的影响
    if (i, target) in dp:
        return dp[(i, target)]
    add = dfs(i+1, target + nums[i])
    sub = dfs(i+1, target - nums[i])
    dp[(i, target)] = add + sub
    return dp[(i, target)]

总结 #

• 优先用key in dict来检查键的存在性，尤其是当字典值可能为0、空字符串等“假值”时，能避免逻辑错误。
• 若一定要用get，必须明确判断返回值是否为None，比如if dp.get((i,t)) is not None:，但这种写法不如in直观简洁。

内容的提问来源于stack exchange，提问作者Ravishankar Chatterjee