数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找最接近的子序列和
假设我们有一个数组 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 的大小
对 nums 进行排序，基于获取 x 的绝对值后的负值
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
从主方法中，执行以下操作：
对于 i 从 0 到 n - 1，执行：
sl := 所有满足 check(x+neg[i], x+pos[i] 为 true 的 s 中的 x 的列表
如果 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))
输入
[0,1,2,3,4], [[3,1],[1,3],[5,6]]
输出
2
374 次浏览
