Pythonの4つのリストからターゲットよりも少ない合計を生成できる一意の4つのインデックスの数を見つけるプログラム

番号A、B、C、およびDの4つのリストがあり、別の番号ターゲットもあるとします。 A [i] + B [j] + C [k] + D[l]≤targetとなるような異なる一意のインデックスi、j、k、lの数を見つける必要があります。

したがって、入力がA =[3、2] B =[5、3] C =[1] D =[2、3] target =9の場合、次のように出力は3になります。組み合わせ：[3、3、1、2] [3、3、1、2] [2、3、1、3]

これを解決するには、次の手順に従います。

• temp_list：=新しいリスト
• 0からAのサイズの範囲のiについては、
  • 0からBのサイズの範囲のjについては、
    • temp_listの最後に（A [i] + B [j]）を挿入します
• リストtemp_listを並べ替える
• ans：=0
• 0からCのサイズの範囲のiについては、
  • 0からDのサイズの範囲のjについては、
    • sum_cd：=C [i] + D [j]
    • sum_ab：=target --sum_cd
    • ans：=ans+合計が<=sum_ab
    であるtemp_list内の要素の数
• 回答を返す

理解を深めるために、次の実装を見てみましょう。

例

from bisect import bisect_right

class Solution:
   def solve(self, A, B, C, D, target):
      temp_list = []
      for i in range(len(A)):
         for j in range(len(B)):
            temp_list.append(A[i] + B[j])

      temp_list.sort()

      ans = 0
      for i in range(len(C)):
         for j in range(len(D)):
            sum_cd = C[i] + D[j]
            sum_ab = target - sum_cd

            ans += bisect_right(temp_list, sum_ab)

      return ans

ob = Solution()
A = [3, 2]
B = [5, 3]
C = [1]
D = [2, 3]
target = 9
print(ob.solve(A, B, C, D, target))

入力

[3, 2], [5, 3], [1], [2, 3], 9

出力

3