用 Python 编写程序来查找最接近子序列和

pythonserver side programmingprogramming更新于 2025/12/13 5:32:17

假设我们有一个数组 nums 和另一个值 goal。我们想要选择一个 nums 子序列，使得其元素和最接近 goal。换句话说，如果子序列元素和为 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]
- 否则，
  - pos[i] := pos[i+1] + nums[i]
  - neg[i] := neg[i+1]
ans := |goal|
s := 一个新的集合并向其中插入 0
定义一个函数 check() 。这将需要 a、b
如果 b < goal - ans 或 goal + ans < a，然后
- 返回 False
返回 True
从主方法，执行以下操作
对于 0 到 n - 1 范围内的 i，执行
- sl := x 列表，对于 s 中的所有 x，当 check(x+neg[i], x+pos[i] 为真时]
- 如果 sl 的大小与 0 相同，则
  - 退出循环
- s := 来自 sl 的新集合
- 对于 sl 中的每个 x，执行
  - y := x + nums[i]
  - 如果 |y - goal| < ans，则
    - 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))