用 Python 编写程序，查找元素 square 在给定范围内的对数

pythonserver side programmingprogramming更新于 2026/1/11 9:48:17

假设我们有两个数字列表 nums1 和 nums2。还有两个数字 lower 和 upper。我们必须找到对 (i, j) 的数量，使得 lower ≤ nums1[i]^2 + nums2[j]^2 ≤ upper。

因此，如果输入为 nums1 = [5, 3, 2] nums2 = [8, 12, 6] lower = 10 upper = 50，则输出将为 2，因为对数为 (1, 2) 和 (2, 2)

10 <= 3^2 + 6^2 << 50 = 10 <= 45 << 50
10 <= 2^2 + 6^2 << 50 = 10 <= 40 << 50

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

用 nums1 中的每个元素的平方替换它
用 nums2 中的每个元素的平方替换它
n := nums1 的大小
m := nums2 的大小
如果 n > m ，然后
- 交换 nums1 和 nums2
- 交换 n 和 m
nums2 := 对列表 nums2 进行排序
res := 0
对于 nums1 中的每个 e1，执行
- st := 将 (lower - e1) 插入到 nums2 的最左边位置，以便对元素进行排序
- en := 将 (upper - e1) 插入到 nums2 的最右边位置，以便对元素进行排序
- count := en - st
- res := res + count
返回 res

示例

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

from bisect import bisect_left, bisect_right
def solve(nums1, nums2, lower, upper):
   nums1 = [i * i for i in nums1]
   nums2 = [i * i for i in nums2]
   n, m = len(nums1), len(nums2)
   if n > m:
      nums1, nums2 = nums2, nums1
      n, m = m, n
   nums2 = sorted(nums2)
   res = 0
   for e1 in nums1:
      st = bisect_left(nums2, lower - e1)
      en = bisect_right(nums2, upper - e1)
      count = en - st
      res += count
   return res

nums1 = [5, 3, 2]
nums2 = [8, 12, 6]
lower = 10
upper = 50
print(solve(nums1, nums2, lower, upper))