LeetCode 228. Summary Ranges

はじめに

LeetCode 「228. Summary Ranges」の問題をGoで解きました。

問題

https://leetcode.com/problems/summary-ranges/description/

問題文

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

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

和訳
ソートされた一意な整数配列 nums が与えられる。

範囲 [a,b] は、a から b までの整数（を含む）の集合である。

配列中のすべての数値を正確にカバーする、最小のソート済み範囲リストを返せ。つまり、 nums の各要素は、範囲のうちの1つで正確にカバーされ、 x が範囲のうちの1つには含まれるが nums には含まれないような整数 x は存在しない。

リスト内の各範囲[a,b]は次のように出力されなければならない：s
・"a->b" if a != b
・"a" if a == b

例

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

Input: nums = [0,2,3,4,6,8,9]
Output: ["0","2->4","6","8->9"]
Explanation: The ranges are:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

制約

• 0 <= nums.length <= 20
• -231 <= nums[i] <= 231 - 1
• All the values of nums are unique.
• nums is sorted in ascending order.

解答

numsはソート済みであり、数値の差が1であれば1つの範囲として扱いますので、隣り合う数値の差が1より大きいかがポイントになります。
範囲の開始位置をstartとしてnumsを走査し、数値の差が1より大きいときにフォーマットしてrangesに追加するという方法を取りました。

コード

func summaryRanges(nums []int) []string {
	if len(nums) == 0 {
		return []string{}
	}
    
	var ranges []string
	start := nums[0]

	for i := 1; i < len(nums); i++ {
		if (nums[i]) != nums[i-1]+1 {
			ranges = append(ranges, formatRange(start, nums[i-1]))
			start = nums[i]
		}
	}
	// 最後の範囲を追加
	ranges = append(ranges, formatRange(start, nums[len(nums)-1]))

	return ranges
}

func formatRange(start, end int) string {
	if start == end {
		return strconv.Itoa(start)
	}
	return (strconv.Itoa(start) + "->" + strconv.Itoa(end))
}

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(1)