leetcode-228. 汇总区间
1. 题目
给定一个 无重复元素 的 有序 整数数组 nums
。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums
的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums
的数字 x
。
列表中的每个区间范围 [a,b]
应该按如下格式输出:
"a->b"
,如果a != b
"a"
,如果a == b
2. 示例
示例 1:
输入:nums = [0,1,2,4,5,7]
输出:["0->2","4->5","7"]
解释:区间范围是:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
示例 2:
输入:nums = [0,2,3,4,6,8,9]
输出:["0","2->4","6","8->9"]
解释:区间范围是:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
3. 我的题解
func summaryRanges(nums []int) []string {
/*
设置快慢两个指针:
慢指针负责维护当前区间范围的起点
快指针负责寻找当前区间范围的终点
快慢指针从索引0开始移动:
快指针寻找当前区间范围终点:如果快指针没越界,并且下一个元素与当前元素在同一个区间(当前元素+1=下一个元素),则快指针右移
将[慢指针,快指针]这一区间,转换为字符串后加入结果集
快指针右移一位,进入下一区间的起点
复杂度分析:
时间复杂度:快慢指针分别遍历一遍nums数组,时间复杂度为O(n)
空间复杂度:使用了常数级的指针额外空间,空间复杂度为O(1)
*/
res := make([]string, 0)
n := len(nums)
// 快慢指针从索引0开始移动:
fast := 0
for fast <= n-1 {
slow := fast
// 快指针寻找当前区间范围终点:如果快指针没越界,并且下一个元素与当前元素在同一个区间(当前元素+1=下一个元素),则快指针右移
for fast <= n-2 && nums[fast]+1 == nums[fast+1] {
fast++
}
// 将[慢指针,快指针]这一区间,转换为字符串后加入结果集
rangeStr := fmt.Sprintf("%d", nums[slow])
if slow < fast {
rangeStr += fmt.Sprintf("->%d", nums[fast])
}
res = append(res, rangeStr)
// 快指针右移一位,进入下一区间的起点
fast++
}
return res
}
4. 心得
一道easy题,用到了快慢双指针,慢指针维护汇总区间的起始下标,快指针寻找区间的终止下标,当满足条件时,将区间格式化后append追加到string数组中。用go刷题还是有些不熟练,很多地方有思路但是由于go基础语法不熟练导致用时过长、例如:
创建string数组(strs := make(string,0))、
string数据类型(var str string)、
int转字符串(intToStr := strconv.Itoa(int值))
多熟悉熟悉吧,估计就没问题了!
本文是原创文章,采用 CC BY-NC-ND 4.0 协议,完整转载请注明来自 DoublePeach
评论
匿名评论
隐私政策
你无需删除空行,直接评论以获取最佳展示效果