アルゴリズム-2012/03/30

質問する

任意のarrを受け入れ、要素の和にkと同じものがある場合はtrueを返し、そうでない場合はfalseを返します.

しゅつりょく

arr k answer
[1,4,8] 12  true
[1,3,5] 12 false

に答える

// O(n^2)
function twoSum(arr, k) {
  let fix = 0;
  const len = arr.length;
  let newArr = [];
  while(fix < len-1){
    let firstNum = arr[fix];

     for(let i = fix +1; i < len; i++){
        newArr.push(firstNum + arr[i]);
     }
    fix +=1;
  }
  
  let result = newArr.includes(k);
  return result;
}

// array.sort O(n lg n) + 탐색 O(n) 또는 O(n lg n)
// 
function twoSum2(arr,k){
  const sortArr = arr.sort();
  let prefix = 0;
  let suffix = arr.length-1;
  const len = arr.length;
  
  //while은 false가 되야 멈춤
  while(prefix < suffix){
    //같지 않은 경우 오름차순이므로 suffix만 감소한다면 
    if(sortArr[prefix] + sortArr[suffix] === k){
      return true
    }else{
      if(sortArr[prefix] + sortArr[suffix] > k){
          suffix -=1;  
      } else {
        prefix += 1;
      }
    }
  }
  return false;
}  

// O(n), 공간 복잡도 O(n)

const test = twoSum([1,3,7], 10);
console.log(test);

const test2 = twoSum2([1,3,7], 10);
console.log(test2);

まず基本的にforゲートを2回回り、最初に時間の複雑さn^2の答えを思い浮かべました.
この方法はすべての状況の数を考慮して確認できるという利点があるが,効率に疑問を抱く方法となっている.
そこで、面接官からのアドバイスをもとに、回答を行いました.
バイナリ探索のような方法で行う.
関数が受信したkと同じ、kより大きい、kより小さいかどうかを判断し、場合に応じてprefixとsuffixを増やして関数を持続させ、prefixがsuffixを超えた場合、繰り返し文は終了する.
繰り返し文が終わる前に値が見つからない場合はfalseが返されます.

ps.アルゴリズムはやればやるほど面白くなり、なぜか繰り返し文から考えられる.

ps2. それから、興奮しないでください.お願いします:)...

リファレンス

符号化試験問題