2022/01/27) 4. 連続部分数列2[効率(ダブルポインタアルゴリズム、スライドウィンドウ、ハッシュ)]

1.質問

＜連続部分数列2＞
:N個の数列があります.この数列において、連続部分数列の和が特定の数M以下の数列が何回あるか.
N=5,M=5,数列が:1 3 1 2 3,5の場合,連続部分数列は{1},{3},{1},{1},{2},{2},{2},{2},
{1,3,1},全部で10種類.

2.解決方法

まずこのコードを覚えなければなりません.sum-=arr[lt++]; そして答え=rt-lt+1;

arr[rt]を加えた値がmより小さい場合、rt−lt+1を加えて回答し、mより大きい場合、振り向いて−=arr[lt+]を加算する.

3.正解

        <script>
            function solution(m, arr){
                let answer=0, sum=0, lt=0;
                for(let rt=0; rt<arr.length; rt++){
                    sum+=arr[rt];
                    while(sum>m){
                        sum-=arr[lt++];
                    }
                    answer+=(rt-lt+1);
                }               
                return answer;
            }
            let a=[1, 3, 1, 2, 3];
            console.log(solution(5, a));
        </script>

4.私のコードとの比較と反省

石の頭のような私の頭は本当に感嘆させられます.どこが間違っているのか分からない.復習するので、とりあえずパス.

        <script>
            function solution(m, arr){
                let answer = 0, p2 = 1;
                for(let p1 = 0; p1 < arr.length; p1++){
                    sum = arr[p1];
                    if(sum<=m)answer++;
                    while(sum <= m && p2<arr.length){
                        sum += arr[p2++];
                        if(sum<=m)answer++;
                    }
                }
                return answer;
            }
            let a=[1, 3, 1, 2, 3];
            console.log(solution(5, a));
        </script>