akmhmgc · akmhmgc · Oct 4, 2025 · tokuhirat · Oct 5, 2025 · tokuhirat
diff --git a/209/step1.md b/209/step1.md
@@ -0,0 +1,62 @@
+# step1 何も見ずに解く
+
+愚直に計算すると二重ループになる。numsのサイズは最大で10^5なので間に合わない。
+subarrayの合計を考える時に同じ計算を何回もしたくないので累積和を使って、二分探索を使うと解けそう。
+これだと時間計算量はO(NlogN)で1秒以内に間に合う。
+空間計算量はO(N)
+
+```ruby
+# @param {Integer} target
+# @param {Integer[]} nums
+# @return {Integer}
+def min_sub_array_len(target, nums)
+    nums_size = nums.size
+    prefix_size = nums_size + 1
+    prefix_sums = Array.new(prefix_size, 0)
+    nums.each_with_index { |num, i| prefix_sums[i + 1] = prefix_sums[i] + num }
+
+    min_index_equal_or_greater = lambda do |left, min_val|
+        right = prefix_size
+        while left < right
+            middle = (left + right) / 2
+            if prefix_sums[middle] < min_val
+                left = middle + 1
+                next
+            end
+            right = middle
+        end
+        left == prefix_size ? Float::INFINITY : left
+    end
+
+    min_size = Float::INFINITY
+    nums_size.times do |i|
+        min_val = target + prefix_sums[i]
+        min_index = min_index_equal_or_greater.call(i + 1, min_val)
+        min_size = [min_size, min_index - i].min
+    end
+    min_size == Float::INFINITY ? 0 : min_size
+end
+```
+
+具体的な例を複数考えると、先頭から値を合計していきtarget以上になった時の配列の長さを答えの候補とする。
+そしてtargetより小さくなるまでsubarrayの開始インデックスを進めるという方法で解けることを思いつく。
+
+```ruby
+# @param {Integer} target
+# @param {Integer[]} nums
+# @return {Integer}
+def min_sub_array_len(target, nums)
+    min_size = Float::INFINITY
+    subarray_sum = 0
+    left = 0
+    nums.each_with_index do |num, right|
+        while subarray_sum + num >= target
+            min_size = [min_size, right - left + 1].min
+            subarray_sum -= nums[left]
+            left += 1
+        end
+        subarray_sum += num
+    end
+    min_size == Float::INFINITY ? 0 : min_size
+end
+```
diff --git a/209/step2.md b/209/step2.md
@@ -0,0 +1,70 @@
+# step2 他の方の解答を見る
+## rightを含まないようにする
+https://github.com/SuperHotDogCat/coding-interview/pull/31#discussion_r1647128733
+
+rightをsubarrayに含めない方法
+rightがi + 1の時はsubarrayはiまで合計されているべき。そうなると前のループでnums[i]が長さに足されている
+
+```ruby
+# @param {Integer} target
+# @param {Integer[]} nums
+# @return {Integer}
+def min_sub_array_len(target, nums)
+    min_size = Float::INFINITY
+    prefix_sum = 0
+    left = 0
+    right = 0
+    while right <= nums.size
+        while prefix_sum >= target
+            min_size = [min_size, right - left].min
+            prefix_sum -= nums[left]
+            left += 1
+        end
+        prefix_sum += nums[right] if right < nums.size
+        right += 1
+    end
+    min_size == Float::INFINITY ? 0 : min_size
+end
+```
+
+## 同じ値が入っている時
+https://github.com/olsen-blue/Arai60/pull/50#discussion_r2005919622
+
+> [0, 0, 1, 1, 2, 2] で 1 を探すのだったら何が欲しいのか。
+2が欲しい場合、3が欲しい場合、4が欲しい場合、2-3どれかが欲しい場合。
+
+同じ値がある時一番右の値が欲しいときはどうすれば良いか？欲しい値以下の最も右にあるインデックスを返せばよいと考えてみる。
+これは欲しい値より大きい値で、最も左にあるインデックスのすぐ左を考えると良さそう。
+
+なのでtargetより大きい最小のインデックスを求めることを考える。
+leftより左はtarget以下の値しかないとする
+rightあるいはrightより右はtargetより大きい値しかないとする
+
+targetの位置の分類は以下
+- middleより左
+  - middleを含む右はtargetより大きいと言えるので、right = middleで更新できる
+- middleまたはmiddleより右
+  - middleより左はtargetより小さいと言えるので、left = middle + 1で更新できる
+
+区間を一ずつ狭くするにはmiddleは切り捨て
+
+```ruby
+def at_most(nums, target)
+    left = 0
+    right = nums.size
+    while left < right
+        middle = (left + right) / 2
+        if nums[middle] <= target
+            left = middle + 1
+        else
+            right = middle
+        end
+    end
+    left - 1
+end
+
+at_most([0, 0, 1, 1, 2, 2], 1) #=> 3
+at_most([0, 0], -1) #=> -1
+at_most([0, 1, 2], 3) #=> 2
+```
+
diff --git a/209/step3.md b/209/step3.md
@@ -0,0 +1,21 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Integer} target
+# @param {Integer[]} nums
+# @return {Integer}
+def min_sub_array_len(target, nums)
+    min_size = Float::INFINITY
+    prefix_sum = 0
+    left = 0
+    nums.each_with_index do |num, right|
+        while prefix_sum + num >= target
+            min_size = [min_size, right - left + 1].min
+            prefix_sum -= nums[left]
+            left += 1
+        end
+        prefix_sum += num
+    end
+    min_size == Float::INFINITY ? 0 : min_size
+end
+```
diff --git a/209/step4.md b/209/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正