Python में 4Sum II

मान लीजिए हमारे पास चार सूचियाँ A, B, C, D पूर्णांक मानों की हैं, हमें गणना करनी है कि कितने टपल (i, j, k, l) हैं जैसे कि A[i] + B[j] + C[k] + D[l] शून्य है। मान लें कि सभी A, B, C, D की लंबाई N है जहां 0 ≤ N ≤ 500। याद रखें सभी पूर्णांक -228 से 228 - 1 की सीमा में हैं और परिणाम अधिकतम 231 - 1 होने की गारंटी है। इसलिए यदि इनपुट A = [1, 2], B = [-2, -1], C = [-1, 2], D = [0, 2] हैं, तो आउटपुट 2 होगा। ऐसा इसलिए है क्योंकि दो टपल हैं, वे हैं (0, 0, 0, 1) इसलिए A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0, और दूसरा टपल है (1, 1, 0, 0), A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• sums नामक एक मैप बनाएं
• A में प्रत्येक तत्व i के लिए
  • B में प्रत्येक तत्व j के लिए
    • यदि i + j sums मैप में नहीं है, तो sums[i + j] := 1 सेट करें
    • अन्यथा sums[i + j] का मान बढ़ाएं
• काउंटर := 0
• C में प्रत्येक तत्व i के लिए
  • D में प्रत्येक तत्व j के लिए
    • यदि (-1)*(i + j) sums में है, तो काउंटर := काउंटर + sums[-1 * (i + j)]
• काउंटर लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

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

इनपुट

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

आउटपुट

2