跳转至

228. 汇总区间

题目描述

给定一个  无重复元素 的 有序 整数数组 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)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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]);
    }
}

评论