Hackerrank の「サブ配列の分割」問題の解法を提供します。この問題では、与えられた整数の配列を特定の条件で分割し、特定の部分配列の合計が与えられた目標値と一致するかどうかを判定する必要があります。
以下に、いくつかの方法とそれぞれのコード例を示します。
方法1: ループと合計計算 この方法では、配列を順番にループして、各位置から始まる部分配列の合計を計算します。各合計値を目標値と比較し、一致する場合はカウンタを増やします。最終的にカウンタの値を返します。
def subarray_division(arr, target):
count = 0
for i in range(len(arr)):
total = 0
for j in range(i, len(arr)):
total += arr[j]
if total == target:
count += 1
return count方法2: スライディングウィンドウ この方法では、固定サイズのウィンドウを使用して配列をスキャンします。ウィンドウ内の値の合計を計算し、目標値と比較します。ウィンドウをスライドさせながら配列全体を走査し、一致する場合はカウンタを増やします。
def subarray_division(arr, target):
count = 0
window_sum = 0
window_start = 0
for window_end in range(len(arr)):
window_sum += arr[window_end]
while window_sum > target:
window_sum -= arr[window_start]
window_start += 1
if window_sum == target:
count += 1
return countこれらは一部の解法例です。問題の要件や制約に応じて、さまざまな方法があります。ここで提供した解法は効率的なものではありますが、問題によってはさらなる最適化が可能です。