Ghép Nối Chuyến Xe Buýt Hà Nội

Mô tả

Buổi sáng cao điểm tại bến xe Giáp Bát, cô Mai — điều phối viên của tổng công ty xe buýt Hà Nội — đang vội vã sắp xếp lịch trình. Cô có danh sách n chuyến xe chờ xuất phát, chuyến thứ i đang chở đúng a[i] hành khách. Để tối ưu gasoline và giảm tắc đường, cô muốn ghép đúng hai chuyến lại thành một chuyến siêu xe: tổng số hành khách của hai chuyến phải bằng chính xác K — sức chứa tối đa một siêu xe cho phép.

Trách nhiệm của bạn là giúp cô Mai tìm ra hai chỉ số i và j (với i < j) sao cho a[i] + a[j] == K. Nếu có nhiều cặp hợp lệ, hãy trả về cặp có chỉ số j nhỏ nhất; nếu vẫn còn nhiều cặp có cùng j nhỏ nhất đó, lấy cặp có chỉ số i nhỏ nhất. Trường hợp không tìm được cặp nào, hãy trả về mảng rỗng.

Đầu vào

• Tham số thứ nhất là mảng số nguyên a gồm n phần tử.
• Tham số thứ hai là số nguyên K.

Đầu ra

• Trả về một mảng gồm hai số nguyên theo dạng [i, j] thỏa mãn điều kiện đề bài, hoặc mảng rỗng [] nếu không tồn tại cặp hợp lệ.

Ràng buộc

• 2 ≤ n ≤ 10^5
• -10^9 ≤ a[i] ≤ 10^9
• -2·10^9 ≤ K ≤ 2·10^9
• Đảm bảo luôn tồn tại không quá một cặp đáp án hợp lệ duy nhất khi có kết quả.

Ví dụ

Ví dụ 1:

• Đầu vào: [30, 20, 15, 25], 45
• Đầu ra: [1, 3]
• Giải thích: Ta có a[1] = 20 và a[3] = 25, tổng là 20 + 25 = 45 bằng đúng K. Mặc dù , nhưng chỉ số là nhỏ nhất xuất hiện khi xét theo thứ tự duyệt. Suy ra đáp án là .