파이썬의 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 :=대상 - sum_cd
  - ans :=as + 합이 <=sum_ab
반환

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

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