在Python中查找最接近的子序列总和的程序
假设我们有一个数组nums和另一个值目标。我们想要选择一个nums子序列，使其元素的总和最接近目标。所以换句话说，如果子序列元素的总和是s，那么我们要最小化绝对差|s-goal|。
所以我们必须找到|s-目标|的最小可能值。因此，如果输入类似于nums=[8,-8,16,-1]目标=-3，那么输出将为2，因为选择子序列[8,-8,-1]，总和为-1.绝对差为|-1-(-3)|=abs(2)=2，这是最小值。
示例
让我们看下面的实现来更好地理解
from collections import Counter
def solve(nums, goal):
n = len(nums)
nums.sort(key=lambda x: -abs(x))
neg = [0 for _ in range(n+1)]
pos = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
if nums[i] < 0:
neg[i] = neg[i+1] + nums[i]
pos[i] = pos[i+1]
else:
pos[i] = pos[i+1] + nums[i]
neg[i] = neg[i+1]
ans = abs(goal)
s = set([0])
def check(a, b):
if b < goal - ans or goal + ans < a:
return False
return True
for i in range(n):
sl = [x for x in s if check(x+neg[i], x+pos[i])]
if len(sl) == 0:
break
s = set(sl)
for x in sl:
y = x + nums[i]
if abs(y - goal) < ans:
ans = abs(y - goal)
if ans == 0:
return 0
s.add(y)
return ans
nums = [8,-8,16,-1]
goal = -3
print(solve(nums, goal))输入
[0,1,2,3,4], [[3,1],[1,3],[5,6]]输出结果
2