Chương trình kiểm tra có tồn tại ba phần tử duy nhất có tổng bằng k hay không trong Python

Giả sử chúng ta có một danh sách các số gọi là nums và một giá trị k, chúng ta phải kiểm tra xem có thể tìm được ba phần tử duy nhất trong danh sách có tổng bằng k hay không.

Ví dụ, nếu đầu vào là nums = [11, 4, 6, 10, 5, 1], k = 20, thì đầu ra sẽ là True, vì chúng ta có các số [4, 6, 10] có tổng bằng 20.

Để giải quyết, chúng ta thực hiện các bước sau:

• sắp xếp danh sách nums
• l := 0, r := kích thước nums - 1
• trong khi l < r - 1:
  • t := k - nums[l] - nums[r]
  • nếu nums[r - 1] < t:
    • l := l + 1
    • tiếp tục vòng lặp ngoài
  • với m trong khoảng l + 1 đến r:
    • nếu nums[m] > t:
      • r := r - 1
      • thoát vòng lặp trong
    • nếu nums[m] bằng t, trả về True
• trả về False

Ví dụ

class Solution:
    def solve(self, nums, k):
        nums.sort()
        l, r = 0, len(nums) - 1
        while l < r - 1:
            t = k - nums[l] - nums[r]
            if nums[r - 1] < t:
                l += 1
                continue
            for m in range(l + 1, r):
                if nums[m] > t:
                    r -= 1
                    break
                if nums[m] == t:
                    return True
        return False

ob1 = Solution()
nums = [11, 4, 6, 10, 5, 1]
k = 20
print(ob1.solve(nums, k))

Input

[11, 4, 6, 10, 5, 1], 20

Output

True