【每日一题Day306】LC228汇总区间 | 双指针

汇总区间【LC228】

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

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

列表中的每个区间范围 [a,b] 应该按如下格式输出：

• "a->b" ，如果 a != b
• "a" ，如果 a == b

• 思路

  使用双指针定位连续区间，找到左端点对应的最远右端点

• 实现

  class Solution {public List<String> summaryRanges(int[] nums) {List<String> res = new ArrayList<>();int i = 0, n = nums.length;while (i < n){int j = i;while (j + 1 < n && nums[j + 1] == nums[j] + 1){j++;}if (i != j){res.add(nums[i] + "->" + nums[j]);}else{res.add(nums[i] + "");}i = j + 1;}return res;}
  }
  

  • 复杂度
    • 时间复杂度：$O(n)$
    • 空间复杂度：$O(1)$