Question

228. 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

 

Example 1:

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"

Example 2:

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"

 

Constraints:

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

Solutions

Solution 1: Two Pointers

We can use two pointers $i$ and $j$ to find the left and right endpoints of each interval.

Traverse the array, when $j + 1 < n$ and $nums[j + 1] = nums[j] + 1$, move $j$ to the right, otherwise the interval $[i, j]$ has been found, add it to the answer, then move $i$ to the position of $j + 1$, and continue to find the next interval.

Time complexity $O(n)$, where $n$ is the length of the array. Space complexity $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]);
  }
}