> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/163.-missing-ranges.md).

# 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"]
```

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

```cpp
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;
}
```