Cho một mảng các số nguyên numbers đã được sắp xếp theo thứ tự không giảm và một số nguyên target.
Hãy tìm hai số sao cho tổng của chúng đúng bằng target và trả về các chỉ số của chúng theo hệ 1-indexed: [index1, index2] với 1 <= index1 < index2 <= numbers.length.
Yêu cầu: Chỉ sử dụng O(1) bộ nhớ phụ.
Ví dụ 1:
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Giải thích: numbers[0] + numbers[1] == 2 + 7 == 9. Đổi sang 1-indexed là [1, 2].Định Dạng Đầu Vào (Input)
Dòng 1: Mảng numbers đã sắp xếp
Dòng 2: Số nguyên target
Dòng 2: Số nguyên target
Định Dạng Đầu Ra (Output)
Mảng 2 phần tử chứa chỉ số 1-indexed [index1, index2]
Ràng Buộc (Constraints)
2 <= numbers.length <= 3 * 10^4
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[2, 7, 11, 15]
9
Output:
[1, 2]
Giải thích: 2 + 7 = 9 (vị trí 1 và 2)
Ví dụ 2:
Input:
[2, 3, 4]
6
Output:
[1, 3]
Giải thích: 2 + 4 = 6 (vị trí 1 và 3)
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kỹ thuật Hai Con Trỏ Hai Đầu O(n) Thời Gian & O(1) Bộ Nhớ
Khởi tạo left = 0 và right = n - 1. Tính sum = numbers[left] + numbers[right]:
- Nếu sum == target: Trả về [left + 1, right + 1].
- Nếu sum < target: Tăng left++ để tăng tổng.
- Nếu sum > target: Giảm right-- để giảm tổng.
Dữ liệu đầu vào (Input):
[2, 7, 11, 15]
9
Kết quả kỳ vọng (Expected Output):
[1, 2]
Dữ liệu đầu vào (Input):
[2, 3, 4]
6
Kết quả kỳ vọng (Expected Output):
[1, 3]
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
