4Sum II trong Python

Giả sử chúng ta có bốn danh sách A, B, C, D chứa giá trị nguyên, cần tính số lượng bộ (i, j, k, l) sao cho A[i] + B[j] + C[k] + D[l] = 0. Tất cả A, B, C, D có cùng độ dài N với 0 ≤ N ≤ 500. Tất cả số nguyên nằm trong khoảng -228 đến 228 - 1 và kết quả đảm bảo tối đa 231 - 1. Ví dụ, A = [1, 2], B = [-2, -1], C = [-1, 2], D = [0, 2] cho kết quả 2 vì có hai bộ: (0, 0, 0, 1) và (1, 1, 0, 0).

Để giải quyết, thực hiện các bước sau:

• Tạo một map tên là sums
• Với mỗi phần tử i trong A:
  • Với mỗi phần tử j trong B:
    • Nếu i + j không có trong sums, đặt sums[i + j] := 1
    • Ngược lại, tăng giá trị của sums[i + j]
• counter := 0
• Với mỗi phần tử i trong C:
  • Với mỗi phần tử j trong D:
    • Nếu (-1) * (i + j) có trong sums, counter := counter + sums[-1 * (i + j)]
• Trả về counter

Ví dụ

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:
                    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]

Kết quả

2