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