Tìm các khoảng trống (Missing Ranges) trong C++

Cho mảng số nguyên đã sắp xếp nums và khoảng bao gồm [lower, upper]. Tìm tất cả các khoảng số bị thiếu trong khoảng đó, định dạng: số đơn lẻ "x" hoặc khoảng "x->y".

Ví dụ

Đầu vào: nums = [0, 1, 3, 50, 75], lower = 0, upper = 99
Đầu ra: ["2", "4->49", "51->74", "76->99"]

Thuật toán duyệt tuyến tính

1. Loại bỏ trùng lặp trong nums (dùng set).
2. Khởi tạo curr = lower, duyệt qua các số trong nums (đã lọc) và upper.
3. Nếu curr == nums[i]: tăng cả hai.
4. Ngược lại: bắt đầu một khoảng thiếu tại curr. Tăng curr cho đến khi gặp số có trong nums hoặc vượt upper. Ghi nhận khoảng.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
        vector<long long> arr;
        for (int x : nums) if (arr.empty() || arr.back() != x) arr.push_back(x);
        vector<string> res;
        long long curr = lower;
        for (size_t i = 0; i <= arr.size(); ++i) {
            long long next = (i == arr.size()) ? (long long)upper + 1 : arr[i];
            if (curr < next) {
                if (curr == next - 1) res.push_back(to_string(curr));
                else res.push_back(to_string(curr) + "->" + to_string(next - 1));
            }
            curr = next + 1;
        }
        return res;
    }
};

Độ phức tạp

• Thời gian: O(N) - duyệt mảng một lần.
• Không gian: O(N) cho mảng lọc (có thể O(1) nếu sửa trực tiếp).

Kết quả kiểm thử

Đầu vào: {0,1,3,50,75}, 0, 99
Đầu ra: [2, 4->49, 51->74, 76->99]