在Python中查找最接近的子序列总和的程序
假设我们有一个数组nums和另一个值goal。我们想选择一个nums的子序列,使其元素的总和最接近目标值。换句话说,如果子序列的元素之和为s,则我们希望最小化绝对差异|s-goal|。
因此,我们必须找到|s-goal|的最小可能值。因此,如果输入是nums=[8,-8,16,-1]和goal=-3,则输出将为2,因为选择子序列[8,-8,-1],其总和为-1。绝对差异为|-1-(-3)|=abs(2)=2,这是最小值。
解决这个问题,我们将采取以下步骤−
- n:=nums的大小
-
根据x的绝对值,在获取绝对值后对nums进行排序
-
neg:=创建一个大小为n + 1的数组,并填充为0
-
pos:=创建一个大小为n + 1的数组,并填充为0
-
对于i在范围n-1到0内减少1,执行以下操作
- 如果nums[i]<0,则
- neg[i]:= neg[i+1]+nums[i]
-
pos[i]:= pos[i+1]
- neg[i]:= neg[i+1]+nums[i]
-
否则,
- pos[i]:= pos[i+1]+nums[i]
-
neg[i]:= neg[i+1]
- 如果nums[i]<0,则
-
ans:=|goal|
-
s:=一个新的集合,将0插入其中
-
定义一个函数check()。这将采取a,b
-
如果b
- 返回False
- 返回True
-
从主方法开始,执行以下操作
-
对于i在范围0到n-1,执行以下操作
- 对于所有x s中的x,当check(x+neg[i],x+pos[i])为真时,均列入列表sl
-
如果sl的大小与0相同,则
- 退出循环
- 从sl创建一个新的集合s
-
对于sl中的每个x,执行以下操作
- y:= x+nums[i]
-
如果|y-goal|
-
ans:=|y-goal|
-
如果ans与0相同,则
-
返回0
-
将y插入s
-
返回ans
示例
让我们看一下以下实现,以便更好地理解
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