資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
