연속부분수열1(Two Pointers Algorithm)

투포인트 알고리즘의 전형적인 문제 ( Two Pointers Algorithm )

: 배열 의 값을 연속으로 구해서 특정 값이 나오는 경우의 수를 구하는 문제 

            function solution2(m, arr){
                let answer=0;
                // lt는 sum의 값이 
                let mius=0;
                // 번위내에 있는걸 축적해서 더한 값
                let sum=0;
                for(let plus=0; plus<arr.length; plus++){
                    sum+=arr[plus];
                    if(sum===m) answer++;   
                    // 크거나 같을때 앞에 더한 값은 순으로 빼야합니다. 
                    // mius가 같이 때문에 같아도 빼야 합니다
                    while(sum>=m){
                        sum-=arr[mius++];
                        if(sum===m) answer++;       
                    }
                }    
                console.log(answer);    
                return answer;
            }

• 하나씩(PLUS) 배열의 값을 더해서 누적한다(SUM). 
• 누적된 값(SUM)이 특정 값(M)와 동일하면 카운터(ANSWER) 한다. 
• while : 여기서 누적 된 값(SUM)이 특정값(M)과 크거나 동일해도(>=) 앞에 누적된 값에 더해진 순서대(MIUS)로 하나씩 빼준다.
• 누적된 값이 특정값과 동일하면 또 카운트 한다. 

 

 

 //me 
            function solution(m , a2){
                let asewer ;
                const n = a2.length;
                let cnt = 0;
                for (let i = 0 ; i < n; i++) {
                   let arr = [];    
                   for (let p = 0; p < n - i; p++) {
                    let red = arr.reduce((p,c) => p + c, 0);
                    let el = a2[i+p];
                    if(red === m){
                        cnt++
                    }
                    arr.push(el)
                   }
                }
               return cnt
                
            };

오답노트

• 시간복잡도에도 for문 2가지와 reduce를 사용해서  O(n*n*n)가 넘어간다.
• 제대로 된 값이 안나온다 예제는 강의와 동일하게 나오지만 다른 작은 특정 값과 다른 배열를 쓰면 강의 코드와 값이 다르게 나온다. 
• 원래 2이였던 수의 값을 배제 되어 버린다.