Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, 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"].

 

逐个数组元素遍历，将间隙取出即可。注意两边的情况。

class Solution {public:    vector
     
       findMissingRanges(int A[], int n, int lower, int upper)    {        vector
      
        ret;        if(n == 0)            return ret;        string str;        if(lower < A[0])        {            if(lower < A[0]-1)                str = to_string((long long)lower) + "->" + to_string((long long)A[0]-1);            else                //lower == A[0]-1                str = to_string((long long)lower);            ret.push_back(str);        }        for(int i = 1; i < n; i ++)        {            if(A[i] - A[i-1] < 2)                continue;            if(A[i] - A[i-1] > 2)                str = to_string((long long)A[i-1]+1) + "->" + to_string((long long)A[i]-1);            else                //A[i] - A[i-1] == 2                str = to_string((long long)A[i-1]+1);            ret.push_back(str);        }        if(A[n-1] < upper)        {            if(A[n-1] < upper-1)                str = to_string((long long)A[n-1]+1) + "->" + to_string((long long)upper);            else                //upper == A[n-1]+1                str = to_string((long long)upper);            ret.push_back(str);        }        return ret;    }};
      
     

 

以下是我的测试用例，全部通过：

void display(vector
     
      & ret){    for(int i = 0; i < ret.size(); i ++)    {        cout << ret[i] << " ";    }    cout << endl;}int main(){    Solution s;    int A[1];    //expect: ["0->9"]    vector
      
        ret = s.findMissingRanges(A, 0, 0, 9);    display(ret);    int B[1] = {
   6};    //expect: ["0->5", "7->9"]    ret = s.findMissingRanges(B, 1, 0, 9);    display(ret);    int C[3] = {
   0, 1, 2};    //expect: []    ret = s.findMissingRanges(C, 3, 0, 2);    display(ret);    int D[5] = {
   0, 1, 3, 50, 75};    //expect: ["2", "4->49", "51->74", "76->99"]    ret = s.findMissingRanges(D, 5, 0, 99);    display(ret);}