4Sum II ใน Python

สมมติว่าเรามีสี่รายการ A, B, C, D ของค่าจำนวนเต็ม เราต้องคำนวณจำนวน tuples (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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างแผนที่หนึ่งแผนที่เรียกว่าผลรวม
• สำหรับแต่ละองค์ประกอบ i ใน A
  • สำหรับแต่ละองค์ประกอบ j ใน B
    • ถ้า i + j ไม่ได้อยู่ในแผนที่ผลรวม ให้ตั้งค่า sums[i + j] :=1
    • มิฉะนั้นจะเพิ่มมูลค่าของผลรวม[i + j]
• ตัวนับ :=0
• สำหรับแต่ละองค์ประกอบ i ใน C
  • สำหรับแต่ละองค์ประกอบ j ใน D
    • ถ้า (-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