পাইথনে 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। সব পূর্ণসংখ্যা -2²⁸ থেকে 2²⁸-1 এর মধ্যে এবং ফলাফল গ্যারান্টিড 2³¹-1 এর কম। যেমন A = [1, 2], B = [-2, -1], C = [-1, 2], D = [0, 2] হলে আউটপুট হবে ২। কারণ দুটি টাপল আছে: (0,0,0,1) এবং (1,1,0,0)।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

sums নামক একটি ম্যাপ তৈরি করুন
A-র প্রতিটি উপাদান i জন্য
- B-র প্রতিটি উপাদান j জন্য
  - যদি i+j sums-এ না থাকে, তবে sums[i+j] := 1 সেট করুন
  - অন্যথায় sums[i+j] এর মান ১ বাড়ান
counter := 0
C-র প্রতিটি উপাদান i জন্য
- D-র প্রতিটি উপাদান j জন্য
  - যদি -1*(i+j) sums-এ থাকে, তবে counter := counter + sums[-1*(i+j)]
counter রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বুঝতে:

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]