Two Sum II: Sorted Input
Bạn nhận được một mảng (array) số nguyên numbers được sắp xếp theo thứ tự không giảm và một số nguyên target. Có chính xác một cặp vị trí khác nhau chứa hai giá trị có tổng bằng target. Hãy trả về hai vị trí đó dưới dạng chỉ số bắt đầu từ 0, với chỉ số nhỏ hơn đứng trước.
Hàm
- numbersinteger-array
- mảng số nguyên đã được sắp xếp
- targetinteger
- tổng của hai giá trị phải đạt tới
- Trả vềinteger-array
- hai chỉ số bắt đầu từ 0 [i, j] với i < j và numbers[i] + numbers[j] == target
Ràng buộc
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbersđược sắp xếp theo thứ tự không giảm.- Có đúng một cặp chỉ số
i < jsao chonumbers[i] + numbers[j] == target.
Ví dụ
- Đầu vào
- numbers = [-4, 1, 3, 8, 12]target = 9
- Đầu ra
- [1, 3]
- Giải thích
- 1 nằm ở chỉ số 1 và 8 nằm ở chỉ số 3, và 1 + 8 = 9. Không có cặp nào khác có tổng bằng 9: ví dụ, -4 + 12 = 8.
- Đầu vào
- numbers = [2, 2, 5, 7]target = 4
- Đầu ra
- [0, 1]
- Giải thích
- Hai số 2 ở chỉ số 0 và 1 nằm ở hai vị trí khác nhau, nên chúng có thể tạo thành một cặp: 2 + 2 = 4.
- Đầu vào
- numbers = [-10, -3, 0, 6]target = -4
- Đầu ra
- [0, 3]
- Giải thích
- -10 ở chỉ số 0 và 6 ở chỉ số 3 cho ta -10 + 6 = -4. Đáp án có thể bao trùm toàn bộ mảng.
Câu hỏi mở rộng
Bạn có thể giải bài này trong thời gian O(n) với bộ nhớ phụ O(1) không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Mảng đã được sắp xếp. Hãy xem giá trị nhỏ nhất và lớn nhất cùng nhau. Tổng của chúng cho bạn biết điều gì khi nhỏ hơn
target?Nếu giá trị đầu tiên cộng với giá trị cuối cùng quá nhỏ, thì giá trị đầu tiên quá nhỏ đối với mọi đối tác, vì giá trị cuối cùng vốn đã là lớn nhất. Bạn có thể loại bỏ giá trị đó.
Đặt một con trỏ ở mỗi đầu. Khi tổng quá nhỏ, dịch con trỏ bên trái sang phải; khi tổng quá lớn, dịch con trỏ bên phải sang trái. Dừng lại khi tổng bằng
target.
Lời giải
Mảng đã được sắp xếp, và thứ tự đó cho bạn biết nên di chuyển theo hướng nào. Đặt một con trỏ ở mỗi đầu. Nếu tổng quá nhỏ, chỉ giá trị lớn hơn ở bên trái mới có thể giúp; nếu quá lớn, chỉ giá trị nhỏ hơn ở bên phải mới có thể giúp. Mỗi bước loại bỏ hẳn một giá trị, vì vậy chỉ cần duyệt một lần là tìm được cặp giá trị mà không cần thêm bộ nhớ.
Kiểm tra từng cặp
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Thử mọi cặp vị trí i < j và kiểm tra xem numbers[i] + numbers[j] có bằng target không. Vì j bắt đầu ngay sau i, cặp bạn tìm được sẽ có chỉ số nhỏ hơn đứng trước.
Cách này bỏ qua thứ tự đã sắp xếp. Với n = 10^4, có khoảng 5 × 10^7 cặp, và nếu đáp án nằm gần cuối mảng thì bạn phải kiểm tra gần như tất cả các cặp.
Thuật toán
- Lặp qua mọi chỉ số bằng
i. - Lặp
jtừi+1đến chỉ số cuối cùng. - Nếu
numbers[i] + numbers[j]bằngtarget, trả về[i, j].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []Tìm kiếm nhị phân cho từng đối tác
Ý tưởng
Khi cố định numbers[i], giá trị cần ghép với nó chính xác là target - numbers[i]. Khoảng bên phải i đã được sắp xếp, nên tìm kiếm nhị phân (binary search) cho biết liệu có giá trị cần ghép đó hay không chỉ trong O(log n) bước. Chỉ tìm kiếm ở bên phải giúp chỉ số nhỏ hơn đứng trước và ngăn một giá trị ghép với chính nó. Vì cặp này là duy nhất nên bất kỳ kết quả khớp nào cũng là đáp án.
Trong ví dụ đầu tiên, i = 0 cần 13 nhưng không có; i = 1 cần 8 và tìm thấy giá trị đó ở chỉ số 3. Như vậy có n lần tìm kiếm, mỗi lần mất O(log n).
Thuật toán
- Lặp
itừ 0 đếnn-2. - Tính
need = target - numbers[i]. - Tìm kiếm nhị phân
needtrong các chỉ số từi+1đếnn-1. - Nếu tìm thấy tại
mid, trả về[i, mid].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []Hai con trỏ từ hai đầu
Ý tưởng
Xét numbers[left] + numbers[right]. Nếu tổng quá nhỏ, numbers[left] không thể nằm trong đáp án: ngay cả khi ghép với giá trị lớn nhất còn lại, tổng vẫn không đủ lớn. Nếu tổng quá lớn, numbers[right] vẫn vượt quá mục tiêu ngay cả khi ghép với giá trị nhỏ nhất còn lại. Vì vậy, mỗi bước đều loại bỏ một giá trị không thể nằm trong cặp, chứ không loại bỏ chính cặp đó. Hai con trỏ sẽ tìm đến cặp cần tìm sau nhiều nhất n-1 bước, chỉ với hai biến.
Với [-4, 1, 3, 8, 12] và target = 9: -4 + 12 = 8 quá nhỏ, nên left chuyển đến chỉ số 1. Sau đó, 1 + 12 = 13 quá lớn, nên right chuyển đến chỉ số 3. Lúc này, 1 + 8 = 9, và đáp án là [1, 3].
Thuật toán
- Đặt
leftthành 0 vàrightthànhn-1. - Trong khi
left < right, tínhtotal = numbers[left] + numbers[right]. - Nếu
totalbằngtarget, trả về[left, right]. - Nếu
totalnhỏ hơn, cộng 1 vàoleft; nếu lớn hơn, trừ 1 khỏiright.
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
Lỗi thường gặp và trường hợp biên
- Trả về vị trí bắt đầu từ 1. Với
[-4, 1, 3, 8, 12]vàtarget = 9, đáp án là[1, 3], không phải[2, 4]. Trong Lua và R, hãy trừ 1 trước khi trả về. - Lặp với
left <= right. Khi hai con trỏ gặp nhau, tổng sẽ dùng một giá trị hai lần. - Di chuyển con trỏ sai. Tổng quá nhỏ cần một giá trị lớn hơn, và chỉ
leftmới có thể đưa ra giá trị đó. - Loại bỏ các giá trị trùng lặp. Với
[2, 2, 5, 7]vàtarget = 4, ta dùng cả hai số 2, nằm ở các vị trí khác nhau.
Câu hỏi thường gặp3
Độ phức tạp thời gian của Two Sum II là bao nhiêu?
Lời giải dùng hai con trỏ chạy trong thời gian O(n) và dùng thêm O(1) bộ nhớ: mỗi bước di chuyển một con trỏ vào trong, và hai con trỏ gặp nhau sau nhiều nhất n-1 bước. Tìm kiếm nhị phân từng phần tử ghép cặp mất O(n log n), còn kiểm tra mọi cặp mất O(n²).
Tại sao không dùng bảng băm (hash map) như trong bài Two Sum đầu tiên?
Bản đồ băm cũng hoạt động và có độ phức tạp thời gian O(n), nhưng nó lưu trữ tối đa n giá trị. Thứ tự đã sắp xếp giúp bạn không cần dùng lượng bộ nhớ đó: chỉ dựa vào tổng, hai con trỏ đã biết phải di chuyển theo hướng nào. Người phỏng vấn đưa ra phiên bản này để xem bạn có tận dụng thứ tự đã cho hay không.
Khi nào tìm kiếm nhị phân là lựa chọn tốt hơn trong trường hợp này?
Khi một giá trị đã cố định và bạn chỉ cần tìm giá trị đi cùng nó. Nếu numbers[0] phải nằm trong cặp, một lần tìm kiếm nhị phân sẽ tìm ra chỉ số còn lại trong O(log n). Để tìm một cặp chưa biết, cách quét bằng hai con trỏ nhanh hơn n lần tìm kiếm riêng biệt.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def twoSumSorted(numbers, target):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
numbers = [-4, 1, 3, 8, 12] target = 9
Đầu ra mong đợi
[1, 3]