LeetCode生活8日目

はじめに

さて今日もやっていきますか。

neetcode生活、今日で最初のroadmap最終問題です。

Longest Consecutive Sequence

sortされていない整数からなる配列が与えられる。

その配列の要素のうち、連続している数字があればその長さを返せ。

ただし、O(n)の計算量で済ませること。

解法

案外簡単そうかもしれないので頑張っていこう。

def longest_consecutive(nums)
  return 0 if nums.empty?

  nums_set = Set.new(nums)
  max_length = 0

  nums_set.each do |num|
    unless nums_set.include?(num - 1)
      current_length = 1
      current_num = num

      while nums_set.include?(current_num + 1)
        current_num += 1
        current_length += 1
      end

      max_length = [max_length, current_length].max
    end
  end

  max_length
end

num - 1を持つような数字を先頭にするという考えがどうしても思いつかなかった。

まずい。

復習というか解法の暗記みたいになっちゃうけど良いのだろうか。

終わりに

他の回答も見たが似たようなことをやっていた。