用 Python 编写程序来计算集合中最小元素和最大元素之和小于 k 的非空子集

pythonserver side programmingprogramming更新于 2026/2/1 21:00:17

假设我们有一个名为 nums 的数字列表和另一个值 k，我们必须找到非空子集 S 的数量，使得 S 的最小值 + S 的最大值 <= k。我们必须记住子集是多重集。因此，子集中可能存在重复的值，因为它们引用的是列表的特定元素，而不是值。

因此，如果输入为 nums = [2, 2, 5, 6], k = 7，则输出将为 6，因为我们可以创建以下子集，例如:[2], [2], [2, 2], [2, 5], [2, 5], [2, 2, 5]。

为了解决这个问题，我们将遵循以下步骤 −

N := A 的大小
对列表 A 进行排序
ans := 0
j := N - 1
对于范围为 0 到 N 的 i，执行
- while j and A[i] + A[j] > K，执行
  - j := j - 1
- 如果 i <= j 且 A[i] + A[j] <= K，则
  - ans := ans + 2^(j - i)
返回 ans

让我们看看下面的实现以便更好地理解 −

示例

class Solution:
   def solve(self, A, K):
      N = len(A)
      A.sort()
      ans = 0
      j = N - 1
      for i in range(N):
         while j and A[i] + A[j] > K:
            j -= 1
            if i <= j and A[i] + A[j] <= K:
               ans += 1 << (j - i)
      return ans
ob = Solution()
nums = [2, 2, 5, 6]
k = 7 print(ob.solve(nums, k))