在Python中查找最接近的子序列总和的程序

在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]

    • 否则,

      • pos[i]:= pos[i+1]+nums[i]

      • neg[i]:= neg[i+1]

  • 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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程