leetcode：163 缺失的区间

题目来源

• leetcode-VIP：163 缺失的区间

题目描述

给定一个排序的整数数组 nums ，其中元素的范围在 闭区间 [lower, upper] 当中，返回不包含在数组中的缺失区间。

示例：
输入: nums = [0, 1, 3, 50, 75], lower = 0 和 upper = 99,
输出: [“2”, “4->49”, “51->74”, “76->99”]

题目解析

• 数组已经排序，但是并不能二分，因为要求所有的缺失区间
• 因此一次遍历

class Solution {
    
    // 生成"lower->upper"的字符串，如果lower==upper，只用生成"lower"
    std::string miss(int lower, int upper){
    
        std::string left = std::to_string(lower);
        std::string right;
        if(upper > lower){
    
            right = "->" + std::to_string(upper);
        }
        return left + right;
    }
public:
    std::vector<std::string> missing_ranges(vector<int>& nums, int low, int high) {
    
        std::vector<std::string> ans;
        for (int curr : nums) {
    
            if(curr > low){
    
                ans.push_back(miss(low, curr - 1));
                low = curr + 1;
            }else if(curr == low){
    
                low = curr + 1;
            }
            
            if(curr == high){
    
                return ans;
            }
        }
        if(low <= high){
    
            ans.push_back(miss(low, high));
        }
        return ans;
    }
};