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ó tồn tại bốn phần tử duy nhất trong danh sách mà tổng bằng k hay không.
Ví dụ, nếu đầu vào là nums = [11, 4, 6, 10, 5, 1], k = 25, thì đầu ra sẽ là True, vì chúng ta có [4, 6, 10, 5] có tổng bằng 25.
Để giải quyết, chúng ta thực hiện các bước sau:
- sắp xếp danh sách nums
- n := kích thước nums
- với i trong khoảng 0 đến n - 4:
- với j trong khoảng i + 1 đến n - 3:
- l := j + 1, h := kích thước nums - 1
- trong khi l < h:
- summ := nums[i] + nums[j] + nums[l] + nums[h]
- nếu summ bằng k, trả về True
- ngược lại nếu summ < k, l := l + 1
- ngược lại, h := h - 1
- với j trong khoảng i + 1 đến n - 3:
- trả về False
Ví dụ
class Solution:
def solve(self, nums, k):
nums.sort()
n = len(nums)
for i in range(n - 3):
for j in range(i + 1, n - 2):
l, h = j + 1, len(nums) - 1
while l < h:
summ = nums[i] + nums[j] + nums[l] + nums[h]
if summ == k:
return True
elif summ < k:
l += 1
else:
h -= 1
return False
ob1 = Solution()
nums = [11, 4, 6, 10, 5, 1]
k = 25
print(ob1.solve(nums, k))
Input
[11, 4, 6, 10, 5, 1], 25
Output
True