Python 的 K 前缀

如果我们有一个数字列表 nums 和一个整数 k，我们必须找到最大的可能 i，其中 nums[0] + nums[1] + ... + nums[i] ≤ k。如果不存在有效的 i，我们将返回 -1。

因此，如果输入类似 nums = [4, -7, 5, 2, 6]，k = 5，那么输出将为 3，索引为 3，因为如果我们相加 4+(-7)+5+2 = 4，则小于 k，如果我们添加最后一个元素，它将不再小于 k，因此索引为 3。

为解决此问题，我们将遵循以下步骤 -

  • 对于范围为 nums 大小减 1 的 1，执行
    • nums[i] := nums[i] + nums[i-1]
  • 对于范围为 nums 大小减 1 到 -1，递减 1，执行
    • 如果 nums[i]<=k，那么
      • 返回 i
  • 返回 -1

让我们查看以下实现以获得更好的理解 -

示例

 现场演示

class Solution:
   def solve(self, nums, k):
      for i in range(1,len(nums)):
         nums[i]+=nums[i-1]
         for i in range(len(nums)-1,-1,-1):
            if nums[i]<=k:
                return i
      return -1
ob = Solution()
nums = [4, -7, 5, 2, 6]
k = 5
print(ob.solve(nums, k))

输入

[4, -7, 5, 2, 6], 5

输出

3

更新于： 2020 年 9 月 23 日

405 次浏览

Начните вашу карьеру

Получите сертификат, пройдя курс

Начать
Реклама