# Missing Ranges

<https://leetcode.com/problems/missing-ranges/description/>

> Given a sorted integer array where the range of elements are in the inclusive range \[lower, upper], return its missing ranges.
>
> For example, given \[0, 1, 3, 50, 75], lower = 0 and upper = 99, return \["2", "4->49", "51->74", "76->99"].

## Thoughts

从lower开始, 依次找数是否存在于nums. 存在就++, 不存在就把范围\[next, nums\[i] - 1]写入output, 并把数放到nums\[i] + 1. 最后检查next <= upper, 注意这里别忘了等于号.

## Code

```
class Solution {
    public List<String> findMissingRanges(int[] nums, int lower, int upper) {
        List<String> res = new ArrayList<>();
        long next = lower;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < next) {
                continue;
            }
            if (nums[i] == next) {
                next++;
                continue;
            }
            if (next == nums[i] - 1) {
                res.add(String.valueOf(next));
            } else {
                res.add(next + "->" + (nums[i] - 1));
            }
            next = (long)nums[i] + 1;
        }

        if (next <= upper) {
            if (next == upper) {
                res.add(String.valueOf(next));
            } else {
                res.add(next + "->" + upper);
            }
        }

        return res;
    }

}
```

## Analysis

时间复杂度O(N).