[条件]
1.配列 ary はソートされている。
2.N は ary の最大値以上
上記条件をみたすような一般の ary、N に対し、
連続 i (> 0) 個の和が N 以下の組み合わせの総数の求めたいと考えています。
どのように求めるのが効率的でしょうか?
例を示しますので、「下記の非効率な箇所」もしくは「より効率的な求め方」
を教えて頂けたら、幸いです。
N = 10
ary = (1..N).to_a # 最大値がN以下の(ソートされた)配列の例
size = ary.size
cnt = size
# 連続i(> 1)個取り出す
i = 2
i_sum = ary[0] + ary[1]
sum = i_sum
while sum <= N
j = 0
while sum <= N
cnt += 1
j += 1
break if j > size - i
# 再計算せず前の結果を利用
sum = sum - ary[j - 1] + ary[i - 1 + j]
end
i += 1
# 再計算せず前の結果を利用
i_sum += ary[i - 1]
sum = i_sum
end
p cnt