The Smallest Window I から考える。
int sum = 0; int left; int right = 0; for(left = 0; left < num; left++) { for(; right < num; right++) { if(sum >= limit) break; sum += arr[right]; } if(sum < limit) continue; #ifdef DEBUG printf("%d: [%d, %d)\n", sum, left, right); #endif ans = min(ans, right - left); sum -= arr[left]; // if(left == right) right++; }
変数名を
i,jよりもleft,rightとしておくほうがわかりやすい。文字通り区間の左がleftで右がright。leftを外側のループに、rightを内側のループにする。leftは1歩ずつ進むようにする。
leftを最小限の移動で留めることでバグを少なくできる。また、最初にint right = 0;とすることでしゃくとり法の計算量がO(N)になる。配列のサイズが決まっている & left, rightの前進の仕方も決まっているので、whileよりもfor文にするほうが配列のout-of-rangeを起こさず安全。
rightのループはbreak文を手前に持ってくる。こうすることで、leftが前進したときもrightが更新されない状態を作り出せる。
left, rightの値が確定したとき、left, rightは半開区間の形になる。つまり、
[left, right)でrightはギリギリ満たさないようなindexer。こうすると、確定した区間の個数がright-leftで求めることができ、+1や-1などの余計な数字が出なくなって嬉しい。left==rightとなる場合(つまり区間の長さが0になる場合)がある。そのままにしておくと、leftのほうがrightよりも右に来てしまうのでバグる。この場合は、if(left == right) right++;のようにrightを強制的に前進させる。(The Smallest Window Iは必ず区間の長さが1以上になるので、この条件を書く必要はない。sum -= arr[left];のようにleftのループの最後に区間に必要な値を更新する。
自分は添字を動かす系の苦手だったので、4番目くらいまでを把握して置くことで、後は問題文に従ってしゃくとり法を惰性でスラスラかけるようになった。
