Cho một mảng các số nguyên nums và một số nguyên target. Hãy tìm vị trí (chỉ số index) của hai phần tử trong mảng sao cho tổng của chúng đúng bằng target.
Quy ước:
- Mỗi bộ kiểm thử luôn đảm bảo có chính xác một cặp đáp án hợp lệ.
- Bạn không được sử dụng cùng một phần tử tại một chỉ số hai lần.
- Có thể trả về kết quả theo thứ tự chỉ số bất kỳ.
Ví dụ 1:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Giải thích: Vì nums[0] + nums[1] == 2 + 7 == 9, nên trả về [0, 1].Ví dụ 2:
Input: nums = [3, 2, 4], target = 6
Output: [1, 2]Định Dạng Đầu Vào (Input)
Dòng 1: Mảng số nguyên nums (ví dụ: [2, 7, 11, 15])
Dòng 2: Số nguyên target
Dòng 2: Số nguyên target
Định Dạng Đầu Ra (Output)
Mảng gồm 2 phần tử chứa chỉ số: [index1, index2]
Ràng Buộc (Constraints)
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[2, 7, 11, 15]
9
Output:
[0, 1]
Giải thích: nums[0] + nums[1] == 2 + 7 == 9
Ví dụ 2:
Input:
[3, 2, 4]
6
Output:
[1, 2]
Giải thích: nums[1] + nums[2] == 2 + 4 == 6
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.
Phương Pháp Giải Two Sum
Khi duyệt qua từng số x tại chỉ số i, ta tính phần bù complement = target - x. Kiểm tra xem complement đã tồn tại trong Hash Map chưa:
- Nếu có: Trả về
[map[complement], i]. - Nếu chưa: Lưu giá trị hiện tại cùng chỉ số vào map:
map[x] = i.
Độ phức tạp: O(n) thời gian và O(n) không gian lưu trữ.
Dữ liệu đầu vào (Input):
[2, 7, 11, 15]
9
Kết quả kỳ vọng (Expected Output):
[0, 1]
Dữ liệu đầu vào (Input):
[3, 2, 4]
6
Kết quả kỳ vọng (Expected Output):
[1, 2]
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...
