three sum

조건

满足a+b+c=0？找出数组S中所有满足条件的三元组
非降序 a≤b≤c
解集中不能包含重复的三元组 O(n^2)

생각, 주의할 점

• 조건에 세가지 수는 크기가 a≤b≤c이므로 다 loop 돌릴 필요없다.
• 먼저 sort를 하고 찾자
  
• 답에 중복이 없다 ([[-1,0,1], [0,-1,1]] 이런경우 안 됌) => map，set
• 중복인지 아는법 join을 사용해서 array를 string으로 변환후 map 비교
• 처음 숫자가 0보다 클시 다음for로 넘어간다.(sort된 배열에서 세 수의 합이 반드시 0보다 크기 때문)

오답

a≤b≤c 인데 쓸데없이 for을 썼다.

function threeSum(num) {
  const map = new Map();
  if (num.length < 3) return [];
  const sortedNum = num.sort((a, b) => a - b);

  for (let a = 0; a < sortedNum.length - 1; a++) {
    for (let b = a + 1; b < sortedNum.length; b++) {
      const sum = sortedNum[a] + sortedNum[b];
      const complement = 0 - sum; // -1*sum, -sum (x)
      const complementIdx = sortedNum.indexOf(complement);

      if (
        sortedNum.includes(complement) &&
        a !== complementIdx &&
        b !== complementIdx
      ) {
        const sortedKey = [sortedNum[a], sortedNum[b], complement]
          .sort()
          .join("");
        if (!map.has(sortedKey)) {
          map.set(sortedKey, [sortedNum[a], sortedNum[b], complement]);
        }
      }
    }
  }
  return Array.from(map.values());
}

정답

function threeSum(num) {
  let map = new Map();
  if (num.length < 3) return [];
  // sort
  num.sort((a, b) => a - b);

  for (let i = 0; i < num.length - 1; i++) {
    if (num[i] > 0) continue;
    let j = i + 1;
    let k = num.length - 1;

    while (j < k) {
      let sum = num[i] + num[j] + num[k];
      if (sum === 0) {
        const key = [num[i], num[j], num[k]].join("");
        if (!map.has(key)) {
          map.set(key, [num[i], num[j], num[k]]);
        }
        j++; // 찾고 난뒤 j 한 칸 더 이동하고 또 찾는다.[-2, 0, 1, 1, 2] // [[-2,0,2],[-2,1,1]]
      } else if (sum < 0) {
        j++;
      } else if (sum > 0) {
        k--;
      }
    }
  }
  return Array.from(map.values());
}

console.log(threeSum([4, -2, -2, 4])); // [[-2,-2,4]]
console.log(threeSum([0])); // []
console.log(threeSum([-2, 0, 1, 1, 2])); // [[-2,0,2],[-2,1,1]]
console.log(threeSum([-10, 0, 10, 20, -10, -40])); //[[-10,-10,20],[-10,0,10]]

console.log(threeSum([0, 0, 0])); // [[0,0,0]]
console.log(threeSum([0, -1, 1])); // [[-1,0,1]]
console.log(threeSum([-4, -2, -2, -2, 0, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6])); //[[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2]]
console.log(threeSum([-4, -2, 1, -5, -4, -4, 4, -2, 0, 4, 0, -2, 3, 1, -5, 0])); // [[-5,1,4],[-4,0,4],[-4,1,3],[-2,-2,4],[-2,1,1],[0,0,0]]

효율적으로 생각하는게 더 쉬운 답이였다.