Caterpillar(애벌레)가 기어가듯이 선형으로 arr의 인덱스를 옮겨가는 방법. 시간 복잡도를 조금 줄일 수 있는 장점이 있다.

문제

배열에서 구간합이 s인 배열이 있는지 확인

코드

const solution = (A, s) => {
  let len = A.length;
  let tail = 0;
  let total = 0;
  for(let head=0; head<len; head++){
    while(tail<len && total+A[tail]<=s){
      total+=A[tail];
      tail++;
    }
    if(total===s) return true;
    total -= A[head];
  }
  return false;
}

삼각형을 이룰 수 있는 원소 찾기

const solution = (A) => {
  let sortedA = A.sort((a, b) => a-b);
  let len = A.length;
  let count = 0;
  for(let x=0; x<len-2; x++){
    let z = x+2;
    for(let y=x+1; y<len-1; y++){
      while(z<len && sortedA[x]+sortedA[y]>sortedA[z]){
        z++;
      }
      count += z-y-1;
    }
  }
  return count;
}

합의 절대값이 가장 작은 두 원소 찾기

const solution = A => {

  let sorted = A.sort((a, b) => a-b);
  let min = Infinity;
  let [start, end] = [0, A.length-1];

  while(start<=end){
    min = Math.min(min, Math.abs(sorted[start]+sorted[end]));
    if(sorted[start]+sorted[end]>0) end--;
    else start++;
  }
  return min;
}