228-汇总区间

LeetCode 228. Summary Ranges

LeetCode-228

You are given a sorted unique integer array nums.

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b]in the list should be output as:

"a->b" if a != b
"a" if a == b

Example 1:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Example 2:

Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

method

类似于双指针，如果满足nums[i+1] == nums[i] + 1指针就一直后移，最后找到满足两两差一的区间[start, i]

vector<string> summaryRanges(vector<int>& nums) {
    int n = nums.size();
    vector<string> res;
    int i = 0;
    while (i < nums.size()) {
        int start = i;
        while (i < n - 1 && nums[i] == nums[i + 1] - 1) i++;
        if (start != i) {
            res.push_back(to_string(nums[start]) + "->" + to_string(nums[i]));
        }
        else res.push_back(to_string(nums[i]));
        i++;
    }
    return res;
}

---

LeetCode 163. 缺失的区间

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

示例：

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

method

如果前面那个数prev+1小于当前数num-1，说明这是一个缺失的区间
如果前面那个数prev+1等于当前数num-1，说明这是一个缺失的数

vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    vector<string> res;
    int prev = lower - 1;
    nums.push_back(upper + 1);
    for (auto& num : nums) {
        if (prev + 1 < num - 1) {
            res.push_back(to_string(prev + 1) + "->" + to_string(num - 1));
        }
        else if (prev + 1 == num - 1) {
            res.push_back(to_string(prev + 1));
        }
        prev = num;
    }
    return res;
}