要素の正方形がPythonで指定された範囲内にあるペアの数を見つけるプログラム

nums1とnums2の2つの番号のリストがあるとします。また、下と上の2つの数字があります。 lower≤nums1[i]^2 + nums2 [j]^2≤upperとなるペアの数（i、j）を見つける必要があります。

したがって、入力がnums1 =[5、3、2] nums2 =[8、12、6] lower =10 upper =50の場合、ペアは（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：=要素がソートされるようにnums2に挿入する左端の位置（下-e1）
  • en：=要素がソートされるようにnums2に挿入する右端の位置（上-e1）
  • count：=en --st
  • res：=res + count
• return 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))

入力

[5, 3, 2], [8, 12, 6], 10, 50

出力

2