[21/08/16 KATA NINJA] leetcode #1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let check=0;check<nums.length;check++){
        const first = nums[check]
        for(let check1=check+1;check1<nums.length;check1++){
            const second = nums[check1]
            
            if(first+second===target) return [check,check1] 
        }
    }
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let answer = []
    const numsIdx = nums.map((i,idx)=>idx)
    function DFS(array,r){
        if(r === 1){            
            return array.map(i=>[i]);
        }
        let result = []
        array.forEach((i,idx) => {            
            const dfs = DFS(array.slice(idx+1),r-1);
            const s = dfs.map(a => [i,...a]);
            result.push(...s);            
        })
        return result;
        
    }
    
   
    
    const combination = DFS(numsIdx,3);
    combination.forEach(i=>{
        let result = 0;
        let array = []
        i.forEach(a=>{
            result += nums[a];
            array.push(nums[a]);
        })
        if(result === 0){
            array = array.sort((a,b)=>a-b);
            answer[`${array[0]}${array[1]}${array[2]}`] = array;
        }
    })
    
    return Object.keys(answer).map(key=>answer[key]);

};

上記のように、答えは正しいですが、タイムアウトもあります.
この問題は二重ポインタアルゴリズムで解決しなければならない.

ダブルポインタ復習

名前の通り、2つのポインタを使用して放出する方法=>完全に時間を短縮できます.

2つのアレイの整列と結合

[1,5,6]
[2,8]
このパラメータが与えられている場合、問題は=>[1,2,5,6,8]に設定されます.
下のように解くことはできません.sort自体の複雑さはO(nlogn)である.

 function solution(arr1, arr2) {
     return [...arr1, ...arr2].sort();
 }

下図のように
O(n+m)で終わることができます.

function solution(arr1, arr2) {
  let answer = [];
  let p1 = 0;
  let p2 = 0;
  while (p1 !== arr1.length && p2 !== arr2.length) {
    answer.push(arr1[p1] > arr2[p2] ? arr2[p2++] : arr1[p1++]);
  }
  return p1 === arr1.length
    ? [...answer, ...arr2.slice(p2)]
    : [...answer, ...arr1.slice(p1)];
}

公共の要素を求めます

[1,2,3,4,5]
[3,4,5,6,7]
=>3,4,5が与えられた場合、ダムを選択します.
解はBABOです.filterもすべての要素を巡回し,includeもすべての要素を巡回するのでO(n^2)となる.

  return arr2.length > arr1.length
    ? arr2.filter((_) => arr1.includes(_))
    : arr1.filter((_) => arr2.includes(_));

2つのポインタで緩めます.次のようにします.

function solution(arr1, arr2) { 
  let answer = [];
  let p1 = 0;
  let p2 = 0;

  // 우선 소팅을 해준다.
  arr1.sort((_, __) => _ - __);
  arr2.sort((_, __) => _ - __);

  
  
  // 양쪽을 순회하면서 작은 쪽의 값을 올려준다.
  
  
  // 소팅이 되어있으므로, 작은 값을 올리게 되면 큰 값과 비교했을 때 같은 값이 나올 수 있다.
  
  
  // 큰 값을 올리게되면, 죽어도 같은 값은 나올 수 없다. (순회 끝까지 가더라도)
  while (p1 !== arr1.length && p2 !== arr2.length) {
    if (arr1[p1] === arr2[p2]) {
      answer.push(arr1[p1]);
      p2++;
      p1++;
    } else {
      arr1[p1] > arr2[p2] ? p2++ : p1++;
    }
  }
  console.log(answer);
}

部分数列の和

[1,2,1,3,1,2]および6
2つのポインタで解くことができます.

let p1 = 0;
  let p2 = 0;
  let answer = [];
  while (p1 !== arr.length && p2 !== arr.length) {
    const result = arr.slice(p1, p2 + 1).reduce((a, b) => a + b);
    if (result > m) {
      // 모두 더한 값이 크면, 왼쪽포인터 값을 올려야 한다. 크기 때문에 더 값을 더해봤자 의미 없다.
      p1++;
    } else {
      if (result === m) {
        
        // 모두 더한 값이 같다면, 왼쪽 포인터 값을 올린다. 마찬가지로 값을 더해봤자 m은 나올 수 없다.(양수만 있다고 가정하면)
        answer.push(arr.slice(p1, p2 + 1));
        p1++;
      } else {
        
        // 값이 더 작다면, 오른쪽 포인터 값을 올린다. 오른쪽 값을 올리게되면 m이 나올 수 있다.
        p2++;
      }
    }
  }

部分数列の和が特定の値を下回る

その名の通り、特定値以下の部分数列の個数を求めればよい.

function solution(arr, m) {
  // 갯수를 구하는 것이기 때문에 야매로
  let p1 = 0;
  let p2 = 0;
  let answer = 0;
  while (p1 !== arr.length && p2 !== arr.length) {
    const result = arr.slice(p1, p2 + 1).reduce((a, b) => a + b);
    if (result <= m) {
      answer += p2 - p1 + 1;
      p2++;
    } else {
      p1++;
    }
  }
  return answer;
}
console.log(solution([1, 3, 1, 2, 3], 5));