3Sum ใน Python - หาสามตัวเลขที่ผลรวมเป็นศูนย์

สมมติว่าเรามีอาร์เรย์ตัวเลข เก็บ n จำนวนเต็ม มีสามองค์ประกอบ a, b, c ในอาร์เรย์ ที่ a + b + c = 0 หา unique triplets ทั้งหมดที่ตรงเงื่อนไข ตัวอย่าง [-1,0,1,2,-1,-4] ผลลัพธ์ [[-1, 1, 0], [-1, -1, 2]]

ขั้นตอนการทำงาน (Two Pointers after Sorting)

1. เรียงลำดับอาร์เรย์ nums, กำหนด res array
2. วนลูป i จาก 0 ถึง len(nums) - 3:
   • ถ้า 0 and nums[i] == nums[i-1] ข้าม (กันซ้ำ)
   • l := i + 1, r := len(nums) - 1
   • วนลูป while l < r:
     • sum := nums[i] + nums[l] + nums[r]
     • ถ้า sum < 0: l += 1 ถ้า sum > 0: r -= 1
     • มิฉะนั้น ใส่ [nums[i], nums[l], nums[r]] ลง res
     • ข้ามค่าซ้ำ: while l < len(nums)-1 and nums[l] == nums[l+1]: l += 1
     • ข้ามค่าซ้ำ: while r > 0 and nums[r] == nums[r-1]: r -= 1
     • l += 1, r -= 1
3. คืนค่า res

ตัวอย่างโค้ด (Python)

class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        result = []
        for i in range(len(nums)-2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
                sum = nums[i] + nums[l] + nums[r]
                if sum < 0:
                    l += 1
                elif sum > 0:
                    r -= 1
                else:
                    result.append([nums[i], nums[l], nums[r]])
                    while l < len(nums)-1 and nums[l] == nums[l+1]:
                        l += 1
                    while r > 0 and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1
                    r -= 1
        return result

ob1 = Solution()
print(ob1.threeSum([-1,0,1,2,-1,-4]))

อินพุต

[-1,0,1,2,-1,-4]

เอาต์พุต

[[-1,-1,2],[-1,0,1]]