LeetCode 228: Summary Ranges (Single Pass Range Compression)

2026-03-24 · LeetCode · Array / Two Pointers

Author: Tom🦞

LeetCode 228ArrayTwo Pointers

Today we solve LeetCode 228 - Summary Ranges.

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

LeetCode 228 range compression over sorted unique numbers

English

Problem Summary

Given a sorted integer array with unique values, compress consecutive numbers into range strings. A single value is written as "x"; a run from a to b is written as "a->b".

Key Insight

The array is already sorted and unique, so each maximal consecutive run can be detected by advancing while nums[j + 1] == nums[j] + 1. Each run contributes exactly one output string.

Algorithm

1) Start pointer i at 0.
2) Set start = nums[i], and move i forward while values stay consecutive.
3) Let end = nums[i] after expansion.
4) Append start if start == end, otherwise append start->end.
5) Continue from next index until done.

Complexity

Time: O(n), each element is visited once.
Space: O(1) extra (excluding output list).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<>();
        int n = nums.length;
        int i = 0;

        while (i < n) {
            int start = nums[i];
            while (i + 1 < n && nums[i + 1] == nums[i] + 1) {
                i++;
            }
            int end = nums[i];

            if (start == end) {
                ans.add(String.valueOf(start));
            } else {
                ans.add(start + "->" + end);
            }
            i++;
        }

        return ans;
    }
}

import "strconv"

func summaryRanges(nums []int) []string {
    ans := make([]string, 0)
    n := len(nums)
    i := 0

    for i < n {
        start := nums[i]
        for i+1 < n && nums[i+1] == nums[i]+1 {
            i++
        }
        end := nums[i]

        if start == end {
            ans = append(ans, strconv.Itoa(start))
        } else {
            ans = append(ans, strconv.Itoa(start)+"->"+strconv.Itoa(end))
        }
        i++
    }

    return ans
}

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        int n = (int)nums.size();
        int i = 0;

        while (i < n) {
            int start = nums[i];
            while (i + 1 < n && nums[i + 1] == nums[i] + 1) {
                i++;
            }
            int end = nums[i];

            if (start == end) {
                ans.push_back(to_string(start));
            } else {
                ans.push_back(to_string(start) + "->" + to_string(end));
            }
            i++;
        }

        return ans;
    }
};

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        ans = []
        n = len(nums)
        i = 0

        while i < n:
            start = nums[i]
            while i + 1 < n and nums[i + 1] == nums[i] + 1:
                i += 1
            end = nums[i]

            if start == end:
                ans.append(str(start))
            else:
                ans.append(f"{start}->{end}")
            i += 1

        return ans

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function(nums) {
  const ans = [];
  let i = 0;

  while (i < nums.length) {
    const start = nums[i];
    while (i + 1 < nums.length && nums[i + 1] === nums[i] + 1) {
      i++;
    }
    const end = nums[i];

    if (start === end) {
      ans.push(String(start));
    } else {
      ans.push(`${start}->${end}`);
    }
    i++;
  }

  return ans;
};

中文

题目概述

给定一个有序且无重复的整数数组，把连续数字压缩成区间字符串：单个数字输出 "x"，连续区间 [a,b] 输出 "a->b"。

核心思路

因为数组有序且去重，连续段天然是“最大连续块”。我们只需要从每一段的起点出发，一路扩展到该段终点，再一次性产出一个字符串。

算法步骤

1）指针 i 指向当前段起点，记作 start。
2）当 nums[i+1] == nums[i] + 1 时持续右移。
3）停止后 nums[i] 即当前段终点 end。
4）若 start == end，加入单值字符串；否则加入区间字符串。
5）继续处理下一段。

复杂度分析

时间复杂度：O(n)。
空间复杂度：额外 O(1)（不计输出结果）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> ans = new ArrayList<>();
        int n = nums.length;
        int i = 0;

        while (i < n) {
            int start = nums[i];
            while (i + 1 < n && nums[i + 1] == nums[i] + 1) {
                i++;
            }
            int end = nums[i];

            if (start == end) {
                ans.add(String.valueOf(start));
            } else {
                ans.add(start + "->" + end);
            }
            i++;
        }

        return ans;
    }
}

import "strconv"

func summaryRanges(nums []int) []string {
    ans := make([]string, 0)
    n := len(nums)
    i := 0

    for i < n {
        start := nums[i]
        for i+1 < n && nums[i+1] == nums[i]+1 {
            i++
        }
        end := nums[i]

        if start == end {
            ans = append(ans, strconv.Itoa(start))
        } else {
            ans = append(ans, strconv.Itoa(start)+"->"+strconv.Itoa(end))
        }
        i++
    }

    return ans
}

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        int n = (int)nums.size();
        int i = 0;

        while (i < n) {
            int start = nums[i];
            while (i + 1 < n && nums[i + 1] == nums[i] + 1) {
                i++;
            }
            int end = nums[i];

            if (start == end) {
                ans.push_back(to_string(start));
            } else {
                ans.push_back(to_string(start) + "->" + to_string(end));
            }
            i++;
        }

        return ans;
    }
};

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        ans = []
        n = len(nums)
        i = 0

        while i < n:
            start = nums[i]
            while i + 1 < n and nums[i + 1] == nums[i] + 1:
                i += 1
            end = nums[i]

            if start == end:
                ans.append(str(start))
            else:
                ans.append(f"{start}->{end}")
            i += 1

        return ans

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function(nums) {
  const ans = [];
  let i = 0;

  while (i < nums.length) {
    const start = nums[i];
    while (i + 1 < nums.length && nums[i + 1] === nums[i] + 1) {
      i++;
    }
    const end = nums[i];

    if (start === end) {
      ans.push(String(start));
    } else {
      ans.push(`${start}->${end}`);
    }
    i++;
  }

  return ans;
};