近状 - LeetCode を始めた
（転活のために？）LeetCode を始めた。ちょっと前に HackerRank を知って使っていたけど、LeetCode のほうが解説とかしっかりしてて良い。あとは Submit した後にテストケースが実行されるが、どんな入力でエラーまたはタイムオーバーしているかと言うのが見えて良い（良いと思ったけど、実は良くないかも...）。
AtCoder の Regular Contest, Beginner Contest を受けたりしていたが非定期っぽいし、目的が異なるので結果の閲覧性も違う。ひたすら LeetCode の問題を解いて、自分のための記録としてブログに書くようにしたい。今週末は3つトライして、2つは正解できたけど1つはタイムオーバー（つまりアルゴリズムが良くない）を食らっている。正解した2つについては、その後に解説を読んで、より良いアルゴリズムを追加で実装してみた。
1. Two Sum
単純に二重ループで書いたけど、レンジオブジェクトの境界をミスって無駄に失敗してしまった。より良いアルゴリズムではハッシュマップを使う。とりあえず、まずハッシュマップが使えないか最初に考えるようにしたい。計算量は悪いけど、この問題は正解した。
2. Add Two Numbers
- https://leetcode.com/problems/add-two-numbers/description/
- https://github.com/inohiro/LeetCode/blob/master/2_add_two_numbers/
ListNode を辿ってただの数字にしてから足し算し、桁毎に ListNode のリストにするコードを再帰を使って書いた。より良いアルゴリズムはキャリー（繰り上がり）がある場合に気をつけながら、無限ループで両方のリストを走査する。リストとか配列とかを逐一辿るようなかんたんに思いつくアルゴリズムはだいたい良くないよな...この問題も正解した。
3. Longest Substring Without Repeating Characters
- https://leetcode.com/problems/add-two-numbers/description/
- https://github.com/inohiro/LeetCode/blob/master/3_longest_substring/
この問題は某社を受けたときに遭遇したやつと似てて、毎回ちゃんと解けないやつである... 文字列のすべての位置から、組み合わせを作って、その出現頻度を数える総当りでやると、入力が長い文字列のときに時間がかかりすぎてしまう（TLE）。今回は（も）お手上げなので、解説を読みつつ書き直してみる。
解説での総当りアルゴリズム（解法1）は O(N3) の時間計算量になっているが、私が書いたのは（たぶん） O(N2)。一方、正解になるアルゴリズムでは O(N)。文字列組み立てでは Array#join を使っていたけど、そこは問題なさそうだ
解法2
そもそも、問題の答えとして部分文字列自体は必要なので、文字が重複しない区間の最長の長さだけ持っていれば良い。文字列を文字ごとに見ていくときに、2つの変数を使う。今見ている区間に重複が見つかるまでハッシュマップに書き込んでいく。重複が見つかれば、そこまでの長さ（2つの変数の差）を答えの候補としてキープしておく。重複した文字列はハッシュマップから削除。
2つの変数のインデックスの変化が、尺取り虫みたいに動くのはどこか他の問題で遭遇したような気がしたのでググってみた。
解法3
2つ目のインデックスは一文字一文字動かす必要はなくて、重複が見つかったところまでジャンプすれば良いよねっていう考え方。
こういう振り返りブログをさくっとかけるようにならないと続かないぞ
