पायथन में 4सम II

मान लीजिए कि हमारे पास पूर्णांक मानों की चार सूचियाँ 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]
• काउंटर:=0
• सी में प्रत्येक तत्व के लिए
  • डी में प्रत्येक तत्व j के लिए
    • अगर (-1)*(i + j) रकम में, तो काउंटर :=काउंटर + योग[-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:
               #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