3Sum (Ba tổng) trong Python

Giả sử chúng ta có một mảng số. Nó lưu n số nguyên, tồn tại ba phần tử a, b, c trong mảng sao cho a + b + c = 0. Tìm tất cả các bộ ba duy nhất trong mảng thỏa mãn điều kiện. Ví dụ, nếu mảng là [-1,0,1,2,-1,-4], kết quả sẽ là [[-1, 1, 0], [-1, -1, 2]].

Để giải quyết, chúng ta làm theo các bước sau:

• Sắp xếp mảng nums, và định nghĩa mảng res.
• Với i từ 0 đến độ dài nums - 3:
  • Nếu i > 0 và nums[i] == nums[i-1], bỏ qua phần tiếp theo và tiếp tục.
  • l := i + 1 và r := độ dài nums - 1.
  • Khi l < r:
    • sum := tổng của nums[i], nums[l] và nums[r].
    • Nếu sum < 0, thì l := l + 1, ngược lại khi sum > 0, thì r := r - 1.
    • Ngược lại chèn nums[i], nums[l], nums[r] vào mảng res.
    • Khi l < độ dài nums - 1 và nums[l] == nums[l+1]:
      • Tăng l lên 1.
    • Khi r > 0 và nums[r] == nums[r-1]:
      • Giảm r đi 1.
    • Tăng l lên 1 và giảm r đi 1.
• Trả về res.

Ví dụ (Python)

Xem triển khai sau để hiểu rõ hơn:

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]))

Đầu vào

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

Đầu ra

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