LeetCode 面试经典150题 228.汇总区间，汇总区间，LeetCode面试经典题目精选集

摘要：本书《LeetCode面试经典150题》中包含了一道名为“汇总区间”的经典题目，编号为228。这道题目旨在考察面试者的算法和数据结构应用能力。题目要求解决一个涉及区间汇总的问题，需要处理一系列区间并将它们汇总。解决此问题通常需要运用排序和合并等算法技巧。

给定一个无重复元素的有序整数数组nums。

返回恰好覆盖数组中所有数字的最小有序区间范围列表，也就是说，nums的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于nums的数字，列表中的每个区间范围[a,b] 应按如下格式输出：

"a->b"，a != b

"a"，a == b

思路：

我们可以使用双指针法来解决这个问题，初始化左指针指向数组的第一个元素，右指针指向数组的第二个元素，我们比较当前右指针指向的元素和左指针指向的元素加一的差值，如果差值等于一，说明这两个元素可以组成一个区间，我们就将左指针向右移动一位并继续比较，如果右指针指向的元素比左指针指向的元素加一的值大很多（差值大于一），说明我们需要找到一个新的起始点来形成一个新的区间，于是我们将左指针移动到右指针的位置并重新开始比较，通过这种方式，我们可以遍历整个数组并找到所有的区间范围。

修正后的代码：

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        int left = 0;  // 左指针初始指向第一个元素
        int right = 0; // 右指针初始指向第二个元素（用于初始化）
        int n = nums.length;
        while (right < n) { // 当右指针未到达数组末尾时继续遍历
            // 寻找下一个区间的起始点
            while (right < n && nums[right] == nums[right - 1] + 1) { // 右指针向右移动直到找到下一个区间的起始点或到达数组末尾
                right++; // 更新右指针位置
            }
            // 将找到的区间添加到结果列表中
            if (left == right) { // 如果只有一个数字构成区间，直接输出数字本身
                res.add(String.valueOf(nums[left]));
            } else { // 如果存在多个数字构成区间，输出区间范围 "a->b" 形式的结果字符串
                res.add(nums[left] + "->" + nums[right - 1]); // 左闭右开区间表示法，注意减一处理边界情况（右边界不包含当前右指针指向的元素）
            }
            left = right; // 将左指针移动到右指针的位置作为下一个区间的起始点进行下一次循环查找新的区间范围
        }
        return res; // 返回结果列表
    }
}

性能：时间复杂度 O(n)，空间复杂度 O(1)。