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).