Question

228. 汇总区间

English Version

题目描述

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

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

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

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

 

示例 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"

 

提示：

• 0 <= nums.length <= 20
• -231 <= nums[i] <= 231 - 1
• nums 中的所有值都 互不相同
• nums 按升序排列

解法

方法一：双指针

我们可以用双指针 $i$ 和 $j$ 找出每个区间的左右端点。

遍历数组，当 $j + 1 < n$ 且 $nums[j + 1] = nums[j] + 1$ 时，指针 $j$ 向右移动，否则区间 $[i, j]$ 已经找到，将其加入答案，然后将指针 $i$ 移动到 $j + 1$ 的位置，继续寻找下一个区间。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

class Solution:
  def summaryRanges(self, nums: List[int]) -> List[str]:
    def f(i: int, j: int) -> str:
      return str(nums[i]) if i == j else f'{nums[i]}->{nums[j]}'

    i = 0
    n = len(nums)
    ans = []
    while i < n:
      j = i
      while j + 1 < n and nums[j + 1] == nums[j] + 1:
        j += 1
      ans.append(f(i, j))
      i = j + 1
    return ans

class Solution {
  public List<String> summaryRanges(int[] nums) {
    List<String> ans = new ArrayList<>();
    for (int i = 0, j, n = nums.length; i < n; i = j + 1) {
      j = i;
      while (j + 1 < n && nums[j + 1] == nums[j] + 1) {
        ++j;
      }
      ans.add(f(nums, i, j));
    }
    return ans;
  }

  private String f(int[] nums, int i, int j) {
    return i == j ? nums[i] + "" : String.format("%d->%d", nums[i], nums[j]);
  }
}

class Solution {
public:
  vector<string> summaryRanges(vector<int>& nums) {
    vector<string> ans;
    auto f = [&](int i, int j) {
      return i == j ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[j]);
    };
    for (int i = 0, j, n = nums.size(); i < n; i = j + 1) {
      j = i;
      while (j + 1 < n && nums[j + 1] == nums[j] + 1) {
        ++j;
      }
      ans.emplace_back(f(i, j));
    }
    return ans;
  }
};

func summaryRanges(nums []int) (ans []string) {
  f := func(i, j int) string {
    if i == j {
      return strconv.Itoa(nums[i])
    }
    return strconv.Itoa(nums[i]) + "->" + strconv.Itoa(nums[j])
  }
  for i, j, n := 0, 0, len(nums); i < n; i = j + 1 {
    j = i
    for j+1 < n && nums[j+1] == nums[j]+1 {
      j++
    }
    ans = append(ans, f(i, j))
  }
  return
}

function summaryRanges(nums: number[]): string[] {
  const f = (i: number, j: number): string => {
    return i === j ? `${nums[i]}` : `${nums[i]}->${nums[j]}`;
  };
  const n = nums.length;
  const ans: string[] = [];
  for (let i = 0, j = 0; i < n; i = j + 1) {
    j = i;
    while (j + 1 < n && nums[j + 1] === nums[j] + 1) {
      ++j;
    }
    ans.push(f(i, j));
  }
  return ans;
}

impl Solution {
  #[allow(dead_code)]
  pub fn summary_ranges(nums: Vec<i32>) -> Vec<String> {
    if nums.is_empty() {
      return vec![];
    }

    let mut ret = Vec::new();
    let mut start = nums[0];
    let mut prev = nums[0];
    let mut current = 0;
    let n = nums.len();

    for i in 1..n {
      current = nums[i];
      if current != prev + 1 {
        if start == prev {
          ret.push(start.to_string());
        } else {
          ret.push(start.to_string() + "->" + &prev.to_string());
        }
        start = current;
        prev = current;
      } else {
        prev = current;
      }
    }

    if start == prev {
      ret.push(start.to_string());
    } else {
      ret.push(start.to_string() + "->" + &prev.to_string());
    }

    ret
  }
}

public class Solution {
  public IList<string> SummaryRanges(int[] nums) {
    var ans = new List<string>();
    for (int i = 0, j = 0, n = nums.Length; i < n; i = j + 1) {
      j = i;
      while (j + 1 < n && nums[j + 1] == nums[j] + 1) {
        ++j;
      }
      ans.Add(f(nums, i, j));
    }
    return ans;
  }

  public string f(int[] nums, int i, int j) {
    return i == j ? nums[i].ToString() : string.Format("{0}->{1}", nums[i], nums[j]);
  }
}