1. Description of the topic

228. Summary interval

English description

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 =,1,2,4,5,7 [0] Output: [” 0 – > 2 “, “4 – > 5”, “7”] Explanation: The ranges are: [0, 2] – > [4, 5] “0 – > 2” – > “4 – > 5” (7, 7] — > “7” Example 2:

,2,3,4,6,8,9 Input: nums = [0] Output: [” 0 “, “2 – > 4”, “6”, “8 – > 9]” Explanation: The ranges are: [0, 0] – > “0” (2, 4] – > 2 – > 4 “[6] – > [8, 9]” 6 “- >” 8 – > 9 “Example 3:

Input: nums = []

Output: []

Example 4:

Input: nums = [-1]

Output: [“-1”]

Example 5:

Input: nums = [0]

Output: [“0”]

Constraints:

0 <= nums.length <= 20

-231 <= nums[i] <= 231 – 1

All the values of nums are unique.

Product description

Given an ordered array of integers with no repeating elements, nums.

Returns a list of minimum ordered ranges that cover exactly all the numbers in the array. That is, every element of NUMS is covered by exactly some range, and there is no number X that belongs to a range but is not numS.

Each interval range [a,b] in the list should be printed in the following format:

“A -> B”, if A! = b “a”, if a is equal to b

Example 1:

Input: nums =,1,2,4,5,7 [0] output: [” 0 – > 2 “, “4 – > 5”, “7”] to explain: the range is: [0, 2] — > “0 – > 2” (4, 5) – > “4 – > 5 [7, 7]” – > “7” sample 2:

Input: nums =,2,3,4,6,8,9 [0] output: [” 0 “, “2 – > 4”, “6”, 8 – > “9”] : range is: [0, 0] – > “0” (2, 4] – > 2 – > 4 “[6] – > [8, 9]” 6 “- >” 8 – > 9 “example 3:

Input: nums = [] Output: [] Example 4:

Input: nums = [-1] Output: [“-1”] Example 5:

Input: nums = [0] Output: [“0”]

Tip:

0 <= nums.length <= 20-231 <= nums[I] <= 231-1 All values in NUMs are different

Source: LeetCode link: leetcode-cn.com/problems/su… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

2

Iterate directly, find a continuous integer, convert both ends of the interval into strings for stitching. (This is medium difficulty…)

3. AC code

C++

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        for(int index = 0; index < nums.size(); index++) {
            int start = nums[index];
            while(index + 1 < nums.size() && nums[index] + 1 == nums[index + 1]) {
                index++;
            }
            if(start != nums[index]) 
                ans.push_back(to_string(start) + "->" + to_string(nums[index]));
            else 
                ans.push_back(to_string(start));
        }
        return ans;
    }
};
Copy the code

Java

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<>();
        for(int index = 0; index < nums.length; index++) {
            int start = nums[index];
            while(index + 1 < nums.length && nums[index] + 1 == nums[index + 1]) {
                index++;
            }
            if(start != nums[index])
                ans.add(start + "->" + nums[index]);
            else
                ans.add(start + "");
        }
        return ans;

    }
}
Copy the code

Post a 100% Java code, temporarily do not understand, later study it

class Solution {
    public List<String> summaryRanges(int[] nums) {

        if (nums == null || nums.length == 0) {
            return new ArrayList();
        }
        List<String> strs = new ArrayList(nums.length);
        int startPosition = 0;
        int i = 1;
        StringBuilder builder=new StringBuilder();
        for (; i < nums.length; i++) {
            if (nums[i] != nums[i - 1] + 1) {
                if (startPosition == i - 1) {
                    strs.add(String.valueOf(nums[startPosition]));
                } else {
                    builder.append(nums[startPosition]);
                    builder.append("->");
                    builder.append(nums[i - 1]);
                    strs.add(builder.toString());
                    builder.delete(0,builder.length());
                }
                startPosition = i;
            }
        }
        if (startPosition == i - 1) {
            strs.add(String.valueOf(nums[startPosition]));
        } else {
            builder.append(nums[startPosition]);
            builder.append("->");
            builder.append(nums[i - 1]);
            strs.add(builder.toString());
            builder.delete(0,builder.length());
        }

        return strs;
    }
}
Copy the code

4. The process of solving the problem

The first,

The for loop iterates, concatenating adjacent intervals

​

​

The algorithm is simple, but why does it work like this? (; ‘⌒ `)

​