You need to enable JavaScript to run this app. 如何判断给定数字列表中的元素能否通过求和得到指定目标值
优惠活动
大模型
产品
解决方案
定价
更多

如何判断给定数字列表中的元素能否通过求和得到指定目标值

实现方案

最优解法:位运算法

针对本题正整数子集和的存在性判断需求,且目标值仅为110的场景,位运算实现是最简单同时效率最高的方案,时间复杂度为O(n),全程仅用整数位运算操作,没有额外复杂逻辑。

核心逻辑

用整数的二进制位标记可凑出的和:

  • 初始值mask = 1,对应二进制最低位为1,代表可以凑出和为0的空组合
  • 遍历列表中的每个数字num,执行mask |= mask << num,相当于把当前所有可凑出的和都加上num,更新可凑出的和的集合
  • 最后判断mask的第x位是否为1,为1则代表目标值可凑出,返回True,否则返回False

代码实现(Python)

def can_reach_target(target, num_list):
    mask = 1
    for num in num_list:
        mask |= mask << num
    return (mask >> target) & 1 == 1

# 代入本题参数测试
num_list = [10,10,20,20,20,50,100,200,200]
x = 110
print(can_reach_target(x, num_list)) # 输出结果为 True

补充说明

如果遇到目标值远大于整型位数的场景,可以改用一维动态规划解法,空间复杂度优化为O(target),逻辑也非常简洁:

def can_reach_target(target, num_list):
    dp = [False] * (target + 1)
    dp[0] = True
    for num in num_list:
        for i in range(target, num - 1, -1):
            if dp[i - num]:
                dp[i] = True
    return dp[target]

内容的提问来源于stack exchange,提问作者drunk pedestrian

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.21 02:06:00