如何判断给定数字列表中的元素能否通过求和得到指定目标值
实现方案
最优解法:位运算法
针对本题正整数子集和的存在性判断需求,且目标值仅为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
相关产品推荐
相关产品推荐

