[LeetCode_15] 3 Sum ( by using JavaScript )

Problem

 

How to Solve ?

 

1) For loop

이 문제를 풀기 위해서는 O(n^3) 의 시간 복잡도를 가지는 3중 For Loop를 이용 해야 하기에, 루프를 사용한 풀이는 옳지 않다고 생각을 하였다.

 

 

2) Two Pointer

이 방법은 검색을 통해서 알게 된건데, 부분 집합을 찾아낼 때 굉장히 유용한 알고리즘 인 것 같다.

하지만, 본 문제는 3개의 합이 0인 경우의 값들을 출력 해줘야 하기에 "For loop"으로 맨 앞의 값을 증가시키고 그 뒤의 배열에서 Left, right 라는 임의의 값을 부여함으로써 투포인트를 활용 할 수 있다.

 

참고 링크 : https://www.geeksforgeeks.org/two-pointers-technique/

 

 

1) 최초 주어진 값을 정렬

탐색을 함에 있어서, 정렬을 미리 해주지 않는다면 연산 과정 속에서 필요한 값을 찾는 시간이 증가하기에 우선적으로 정렬을 수행함!

 nums.sort((a, b) => a - b);

 

 

2) For loop

아래와 같이 I의 뒤 배열에 투포인터를 걸어서 탐색을 할 생각이기에, I는 길이보다 2 작은 값까지만 탐색을 합니다.

  for (let i = 0; i < nums.length - 2; i++) {

  }

  // [ -4(i) , -1(left), -1, 0, 1, 2(right) ]

 

3) 시작 조건

  for (let i = 0; i < nums.length - 2; i++) {
      // 음수가 없거나, 양수가 없다면 0을 만들 수 없기에 break 
    if (nums[i] > 0 || nums[nums.length] < 0) {
      break;
    }

    // 중복되는 값인지 점검
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }

}

 

 

 

4) 투포인트 세팅 및 탐색

  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0 || nums[nums.length] < 0) {
      break;
    }

    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }

    // i 뒤 배열의 첫번째 값
    let left = i + 1,
    // i 뒤 배열의 마지막 값
      right = nums.length - 1;


    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum > 0) {
        right -= 1;
      } else if (sum < 0) {
        left += 1;
      } else {
        answer.push([nums[i], nums[left], nums[right]]);

        while (left < right && nums[left] === nums[left + 1]) {
          left++;
        }

        while (left < right && nums[right] === nums[right - 1]) {
          right--;
        }

        left += 1;
        right -= 1;
      }
    }
  }
  return answer;
}

 

5) 전체 코드

function solution(nums) {
  const answer = [];
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0 || nums[nums.length] < 0) {
      break;
    }

    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }

    let left = i + 1,
      right = nums.length - 1;


    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum > 0) {
        right -= 1;
      } else if (sum < 0) {
        left += 1;
      } else {
        answer.push([nums[i], nums[left], nums[right]]);

        while (left < right && nums[left] === nums[left + 1]) {
          left++;
        }

        while (left < right && nums[right] === nums[right - 1]) {
          right--;
        }

        left += 1;
        right -= 1;
      }
    }
  }
  return answer;
}

let nums = [-1, 0, 1, 2, -1, -4];
console.log(solution(nums));

Result

Time Submitted Status Runtime Memory Language

05/15/2021 15:18

Accepted

140 ms

48.7 MB

javascript