[js]선행탐색

선행탐색이란?

[1, 3, 5, 7, 9] 배열이 주어졌을경우 합이 9인 인덱스를 나열하라고하면 (0,2) , (4,4)이다.
탐색을위해 2중 for문을 돌릴 경우 시간복잡도는 n2이 되기에
이경우 선형탐색을한다.

선행탐색법

조건에 따라 왼쪽으로 한칸, 오른쪽으로 한칸씩 이동하여 탐색한다.
인수가 K 라고 주어졌을때 각 index의 합이 K 보다 작은경우 Left++
인수가 K 라고 주어졌을때 각 index의 합이 K와 같은경우 Right++
인수가 K 라고 주어졌을때 각 index의 합이 K와 큰경우 Right++
식으로 탐색하는 방법이다.

프로그래머스 예제 : 연속된 부분 수열의 합

function solution(sequence, k) {
    var answer = [];

    var sum = 0;
    
    // for (let i = 0; i<sequence.length; i++){
            var start = 0;
            var end   = 0;
            var sum = 0;
        while(end<sequence.length){    
        
            if(sum < k) {
                sum = sum + sequence[end];
            }else if(sum == k){
                answer.push([start-1,end]);
                sum = sum - sequence[start-1];
            }else{
                sum = sum - sequence[start-1];
            }
            // console.log(start,end,sum,k);
            if(sum <k){
                end ++;
            }else{
                start ++;
            }
        }
    
    answer.sort((a,b)=>{
        var sortA = Math.abs(a[1]-a[0]);
        var sortB = Math.abs(b[1]-b[0]);
        
        if(sortA == sortB){
            return a[0]-b[0]
        }
        if(sortA != sortB){
            return sortA-sortB
        }
    })
    
    //첫번째 값
    answer = answer[0];
    return answer;
    // }
}