LeetCode 228. Summary Ranges

プログラミング
Page content

どうも、たくチャレ(@takuchalle)です。

LeetCodeの228. Summary Rangesを解いてみました。

設問

昇順に整列済みの数列が与えられます。連続する数列をx -> yという形式 のリストを返す問題。数列の要素数が1の時はxのみを返す。

例えば[0,1,2,4,5,7]という入力であれば、["0->2","4->5","7"]を返します。

解

前方から連続する数列を探していけば良いです。

iを基準に連続する数列を探すようにしました。

見かけ上2重ループになっていますが、同じ要素を探索することはないので、計算量はO(N)で、消費メモリはO(1)です。

class Solution {
   public:
    vector<string> summaryRanges(vector<int>& nums) {
        auto ans = vector<string>();

        for (size_t i = 0; i < nums.size(); i++) {
            int j = i;
            while (j + 1 < nums.size() && nums[j] + 1 == nums[j + 1]) {
                j++;
            }

            if (i == j) {
                ans.push_back(to_string(nums[i]));
            } else {
                ans.push_back(to_string(nums[i]) + "->" + to_string(nums[j]));
            }

            i = j; // jまでは探索済みなので、iを更新します
        }

        return ans;
    }
};