163. Missing Ranges

Given a sorted integer array nums, where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

Example:

Input: nums = [0, 1, 3, 50, 75], lower = 0 and upper = 99,
Output: ["2", "4->49", "51->74", "76->99"]

題目有個重要的假設就是所有給的數字都會在[lower, upper]區間之間，所以在for loop內部不需要確認數字比upper bound大的情況。

string getString(int num1, int num2) {
    return (num1 == num2) ? to_string(num1) : (to_string(num1) + "->" + to_string(num2));
}
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) { // time: O(n); space: O(n)
    vector<string> res;
    long next = lower;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] < next) continue;
        if (nums[i] == next) {
            ++next;
        } else {
            res.push_back(getString(next, nums[i] - 1));
            next = (long)nums[i] + 1;
        }
    }
    if (next <= upper) {
        res.push_back(getString(next, upper));
    }
    return res;
}