leetcode: Summary Ranges (less 1ms) Analysis and solution

PROBLEM:

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Hide Tags

 Array

Show Similar Problems

Analysis:

Logic is simple. The key is how to write a simple and efficient code on it. 

See my first version codes which is awful (please don't read the code and jump to the version 2 in the bottom): 

 //////////////////////////////////////////

//code version 1

class Solution {

public:

    vector<string> summaryRanges(vector<int>& nums) {

     vector<string> result;

     string sTmp;

     //input checking

     if(nums.size()==0)return result;

     sTmp.append(to_string(nums[0]));//change num to char 

     if(nums.size()==1){

        result.push_back(sTmp);

     }

     

     for (int i=1;i<nums.size();i++){

         if (nums[i]-nums[i-1]!=1 ){

             if (sTmp[0]!=(nums[i-1])+48){

             sTmp.push_back('-');

             sTmp.push_back('>');

             sTmp.append(to_string(nums[i-1]));

             result.push_back(sTmp);

             sTmp.clear();

             sTmp.append(to_string(nums[i]));

             }

             else{

                 result.push_back(sTmp);

                 sTmp.clear();

                 sTmp.append(to_string(nums[i]));

             }

         }

         if(i==nums[nums.size()-1]){

             if(nums[i]==sTmp[0]){

                 result.push_back(sTmp);

             }

             else{

             sTmp.push_back('-');

             sTmp.push_back('>');

             sTmp.append(to_string(nums[i]));

             result.push_back(sTmp);

             }

         }

     }

     return result;

     

    }

};

Later, I used following logic/strategy to code it:

 Basically, I use another index j to record the length of consistent numbers. The j will stop when two conditions are met, as shown in the codes. And the codes based on it are shown below, which is much shorter and clearer:

//////////////////////////////////////////////////////////////////////////

//code <1ms

class Solution {

public:

       vector<string> summaryRanges(vector<int>& nums) {

              vector<string> result;

              int N = nums.size();

              for (int i = 0; i<nums.size();){

                     int j = 1;

                     //this loop will stop when reach the end or value is not consistant.

                     //after the loop, j will be the length of consistant numbers

                     for (; j + i<N && nums[i + j] - nums[i + j - 1] == 1; j++){}

                     string sTmp;

                     sTmp.append(j>1 ? to_string(nums[i]) + "->" + to_string(nums[i + j - 1]) : to_string(nums[i]));

                     result.push_back(sTmp);

                     //resume the outer loop with new index, i.

                     i = i + j;

              }

              return result;

       }

};