Question

Formatted question description: https://leetcode.ca/all/228.html

 228. Summary Ranges

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

 Example 1:

 Input:  [0,1,2,4,5,7]
 Output: ["0->2","4->5","7"]
 Explanation: 0,1,2 form a continuous range; 4,5 form a continuous range.

 Example 2:

 Input:  [0,2,3,4,6,8,9]
 Output: ["0","2->4","6","8->9"]
 Explanation: 2,3,4 form a continuous range; 8,9 form a continuous range.

 @tag-array

Algorithm

Traverse the array once and check whether the next number is increasing each time

• If yes, continue to traverse down
• If not, we have to judge whether it is a number or a sequence at this time,
  • A number is directly stored in the result
  • The sequence should be stored in the first and last numbers and the arrow "->".

We need two variables i and j, where i is the position of the starting number of the continuous sequence, j is the length of the continuous sequence,

• when j is 1, it means there is only one number,
• if it is greater than 1, it is a continuous sequence.

Code

Java

• Java
• C++
• Python

• import java.util.ArrayList;
  import java.util.List;
  
  public class Summary_Ranges {
  
      class Solution {
          public List<String> summaryRanges(int[] nums) {
              List<String> result = new ArrayList<>();
              int left = 0, n = nums.length;
              while (left < n) {
                  int right = 1;
                  while (left + right < n && (long)nums[left + right] - nums[left] == right) {
                      ++right;
                  }
                  result.add(
                      right <= 1 ? // note: right here is already after ++ in above loop. so it's actually checking if it's a single digit
                          String.valueOf(nums[left])
                          : String.valueOf(nums[left]) + "->" + String.valueOf(nums[left + right - 1])); // also here, -1 because already done ++
                  left += right;
              }
  
              return result;
  
          }
      }
  }
  

• // OJ: https://leetcode.com/problems/summary-ranges/
  // Time: O(N)
  // Space: O(N)
  class Solution {
  public:
      vector<string> summaryRanges(vector<int>& A) {
          vector<string> ans;
          int start = 0;
          for (int i = 0, N = A.size(); i < N; ++i) {
              if (i + 1 < N && A[i + 1] == A[i] + 1) continue;
              ans.push_back(to_string(A[start]) + (i == start ? "" : ("->" + to_string(A[i]))));
              start = i + 1;
          }
          return ans;
      }
  };
  

• class Solution(object):
    def summaryRanges(self, nums):
      """
      :type nums: List[int]
      :rtype: List[str]
      """
  
      def outputRange(start, end):
        if start == end:
          return str(start)
        return "{}->{}".format(start, end)
  
      if not nums:
        return []
      ans = []
      start = 0
      for i in range(0, len(nums) - 1):
        if nums[i] + 1 != nums[i + 1]:
          ans.append(outputRange(nums[start], nums[i]))
          start = i + 1
      ans.append(outputRange(nums[start], nums[-1]))
      return ans
  
  

All Problems

All Solutions