题目描述:
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return [0->2,4->5,7].
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
就是给定一个已排序的数组,返回一个字符串数组,每个字符串表示为元素区间的合并,
LeetCode Summary Ranges
。本题是典型的two pointer 问题。
思路:
一次遍历,使用two pointer方法,from 表示区间的起始元素,to表示区间的结束元素。
如果相邻元素nums[i]和nums[i-1]差值为1,区间范围+1:to = nums[i] ,注意最后元素的处理。
否则:
如果from不等于to:
将range = [from,to]添加到解集中,并更新from的位置。
如果from和to相等:
将range=from(或to)添加到解集
注意末尾元素的判断(如果已打末尾,添加末尾元素)
实现代码:
public class Solution { public IList<string>SummaryRanges(int[] nums) { if(nums.Length == 0){ return new List<string>(); } if(nums.Length == 1){ return new List<string>(){nums[0].ToString()}; } var from = nums[0]; var to = nums[0]; var ret = new List<string>(); for(var i = 1 ;i < nums.Length; i++){ if(nums[i] - nums[i-1] == 1){ to = nums[i]; if(i == nums.Length - 1){ ret.Add(string.Format({0}->{1}, from , to)); } } else{ if(from != to){ ret.Add(string.Format({0}->{1}, from , to)); if(i == nums.Length - 1 && to != nums[nums.Length - 1]){ ret.Add(nums[i].ToString()); } } else{ ret.Add(from.ToString()); if(i == nums.Length - 1){ ret.Add(nums[i].ToString()); } } from = nums[i]; to = nums[i]; } } return ret; }}</string></string></string></string>