4Sum II bằng Python

Giả sử chúng ta có bốn danh sách A, B, C, D có giá trị nguyên, chúng ta phải tính xem có bao nhiêu bộ giá trị (i, j, k, l) sao cho A [i ] + B [j] + C [k] + D [l] bằng không. Hãy xem xét tất cả A, B, C, D có cùng độ dài N trong đó 0 ≤ N ≤ 500. Hãy nhớ rằng tất cả các số nguyên nằm trong khoảng -228 đến 228 - 1 và kết quả được đảm bảo nhiều nhất là 231 - 1. Vì vậy, nếu các đầu vào là A =[1, 2], B =[-2, -1], C =[-1, 2], D =[0, 2], thì đầu ra sẽ là 2. Điều này là do có hai bộ giá trị, chúng là (0, 0, 0, 1) nên A [0] + B [0] + C [0] + D [1] =1 + (-2) + (-1) + 2 =0 và một bộ giá trị khác là (1, 1, 0, 0), A [1] + B [1] + C [0] + D [0] =2 + (-1) + (-1) + 0 =0

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một bản đồ được gọi là tổng
• cho mỗi phần tử i trong A
  • cho mỗi phần tử j trong B
    • nếu i + j không có trong bản đồ tổng, thì hãy đặt tổng [i + j]:=1
    • nếu không, hãy tăng giá trị của tổng [i + j]
• bộ đếm:=0
• cho mỗi phần tử i trong C
  • cho mỗi phần tử j trong D
    • if (-1) * (i + j) tính bằng tổng, thì counter:=counter + sums [-1 * (i + j)]
• bộ đếm trả lại

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

class Solution(object):
   def fourSumCount(self, A, B, C, D):
      sums ={}
      for i in A:
         for j in B:
            if i+j not in sums:
               sums[i+j] = 1
            else:
               sums[i+j] +=1
      counter = 0
      for i in C:
         for j in D:
            if -1 * (i+j) in sums:
               #print(-1 * (i+j))
               counter+=sums[-1*(i+j)]
      return counter
ob1 = Solution()
print(ob1.fourSumCount([1,2], [-2,-1], [-1,2], [0,2]))

Đầu vào

[1,2]
[-2,-1]
[-1,2]
[0,2]

Đầu ra

2