3Sum bằng Python

Giả sử chúng ta có một mảng số. Nó lưu trữ n số nguyên, có các 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 trường hợp này. Vì vậy, nếu mảng giống như [-1,0,1,2, -1, -4], thì kết quả sẽ là [[-1, 1, 0], [-1, -1, 2]]

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• Sắp xếp các số mảng và xác định res mảng
• cho tôi trong phạm vi từ 0 đến độ dài là num - 3
  • nếu i> 0 và nums [i] =nums [i - 1], thì hãy bỏ qua phần tiếp theo và tiếp tục
  • l:=i + 1 và r:=độ dài của nums - 1
  • trong khi l
  • 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
  • nếu không thì chèn nums [i], nums [l], nums [r] vào mảng res
  • while l <độ dài của nums - 1 và nums [l] =nums [l + 1]
    • tăng l thêm 1
  • while r> 0 và nums [r] =nums [r - 1]
    • giảm r đi 1
  • tăng l thêm 1 và giảm r đi 1

Ví dụ (Python)

Hãy cùng chúng tôi xem cách 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]]