Tìm cặp số có tổng bằng Target trên mảng đã sắp xếp
Trong bài toán ghép cặp tài nguyên máy chủ tại AI Empire Academy, ta có một danh sách numbers gồm các số nguyên đã được sắp xếp theo thứ tự tăng dần và một giá trị mục tiêu target.
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: sorted arrays, two pointers concept.
Nội dung đề bài
Mục tiêu kiến thức
- Hiểu sâu Bất biến vòng lặp (Loop Invariant) của kỹ thuật Hai con trỏ ngược chiều trên mảng đã sắp xếp.
- Giảm độ phức tạp từ duyệt vét cạn O(N2) xuống tuyến tính O(N) với O(1) bộ nhớ phụ.
- Đảm bảo thuật toán không sử dụng thêm cấu trúc dữ liệu bảng băm (Hash Map).
Mô tả bài toán
Trong bài toán ghép cặp tài nguyên máy chủ tại AI Empire Academy, ta có một danh sách numbers gồm các số nguyên đã được sắp xếp theo thứ tự tăng dần và một giá trị mục tiêu target.
Hãy viết hàm two_sum_sorted(numbers: list[int], target: int) -> tuple[int, int] | None tìm hai phần tử ở hai vị trí khác nhau trong mảng sao cho: numbers[i] + numbers[j] == target (với 0 ≤ i < j < len(numbers))
Quy tắc:
- Trả về
tuplegồm hai chỉ số 0-based:(i, j). - Nếu có nhiều cặp thỏa mãn, trả về cặp được tìm thấy đầu tiên bởi thuật toán hai con trỏ co từ hai biên.
- Nếu không tồn tại bất kỳ cặp nào, hàm trả về
None. - Thuật toán bắt buộc phải đạt độ phức tạp thời gian O(N) và bộ nhớ bổ trợ O(1).
Input
numbers: Danh sách các số nguyên đã sắp xếp tăng dần.target: Số nguyên mục tiêu.
Output
Trả về tuple[int, int] là (i, j) hoặc None.
Ràng buộc
- Độ dài N: 0 ≤ N ≤ 105.
- -109 ≤ numbers[k], target ≤ 109.
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
Ví dụ 1
Input
`numbers = [2, 7, 11, 15], target = 9`Output
`(0, 1)`Giải thích
numbers[0] + numbers[1] = 2 + 7 = 9.
Ví dụ 2
Input
`numbers = [1, 3, 4, 6, 8, 11], target = 10`Output
`(1, 3)` (hoặc cặp phù hợp theo hai con trỏ)Giải thích
numbers[1] + numbers[3] = 3 + 6 = 9 eq 10. Tại i=0 (1) + j=5 (11) = 12 > 10 ⇒ j giảm. Cặp numbers[0] + numbers[4] = 1 + 8 = 9 < 10 ⇒ i tăng. Cặp numbers[1] + numbers[4] = 3 + 8 = 11 > 10 ⇒ j giảm. Cặp numbers[1] + numbers[3] = 3 + 6 = 9 < 10 ⇒ i tăng. Cặp numbers[2] + numbers[3] = 4 + 6 = 10 ⇒ Trả về (2, 3).
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.