Java 算法：汇总区间 - 寻找有序数组的最小区间范围列表

Java 算法：汇总区间 - 寻找有序数组的最小区间范围列表

给定一个无重复元素的有序整数数组 nums 。返回恰好覆盖数组中所有数字的最小有序区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

示例：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：数字 0、1、2 被区间 "0->2" 覆盖，数字 4 和 5 被区间 "4->5" 覆盖，数字 7 被区间 "7" 覆盖。

代码实现：

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ranges = new ArrayList<>();
        if (nums.length == 0) return ranges;
        int start = nums[0];
        int end = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == end + 1) {
                end = nums[i];
            } else {
                if (start == end) {
                    ranges.add(String.valueOf(start));
                } else {
                    ranges.add(start + '->' + end);
                }
                start = nums[i];
                end = nums[i];
            }
        }
        if (start == end) {
            ranges.add(String.valueOf(start));
        } else {
            ranges.add(start + '->' + end);
        }
        return ranges;
    }
}

算法思路：

1. 初始化两个变量 start 和 end，分别用来记录当前区间的起始值和结束值，初始值为 nums 的第一个元素。
2. 遍历数组 nums，对于每个元素 nums[i]，判断其是否与当前区间的结束值 end 相邻，即 nums[i] == end + 1。
3. 如果相邻，则更新 end 的值为 nums[i]。
4. 如果不相邻，则将当前区间 [start, end] 添加到 ranges 列表中，并更新 start 和 end 的值为 nums[i]。
5. 最后，将最后一个区间 [start, end] 添加到 ranges 列表中。

算法优化：

• 该算法的时间复杂度为 O(n)，其中 n 为数组 nums 的长度。
• 该算法的空间复杂度为 O(n)，其中 n 为 ranges 列表的大小。
• 可以使用 StringBuilder 来优化字符串拼接的效率。

总结：

本文详细介绍了使用 Java 语言解决“汇总区间”问题的算法思路和代码实现。该算法简单易懂，时间和空间复杂度都比较低，适合处理类似的问题。