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