합이 일부 목표 합과 같은 배열에서 세 요소의 그룹을 찾는 방법 JavaScript

숫자 배열과 targetsum을 취하는 threeSum()과 같은 함수를 작성해야 합니다. 배열에 목표 합계에 해당하는 세 개의 숫자가 있는지 확인합니다. 배열에 이러한 세 개의 숫자가 있으면 배열에 인덱스를 반환해야 합니다. 그렇지 않으면 -1을 반환해야 합니다.

접근

접근 방식은 간단합니다. 먼저 배열과 목표 합계를 취하고 선형 시간과 공간을 사용하여 목표 합계에 합산되는 두 숫자의 인덱스를 반환하는 함수 twoSum()을 작성하고 그렇지 않으면 -1을 반환합니다.

그런 다음 배열의 각 요소를 반복하는 실제 함수 threeSum()을 작성하여 두 번째 요소의 인덱스를 찾습니다. 이 인덱스는 twoSum() 숫자에 더할 때 실제 대상에 합산될 수 있습니다.

따라서 이와 같이 O(N^2) 시간에 세 가지 요소를 찾을 수 있습니다. 이에 대한 코드를 작성해 보겠습니다 -

예시

const arr = [1,2,3,4,5,6,7,8];
const twoSum = (arr, sum) => {
   const map = {};
   for(let i = 0; i < arr.length; i++){
      if(map[sum-arr[i]]){
         return [map[sum-arr[i]], i];
      };
      map[arr[i]] = i;
   };
   return -1;
};
const threeSum = (arr, sum) => {
   for(let i = 0; i < arr.length; i++){
      const indices = twoSum(arr, sum-arr[i]);
      if(indices !== -1 && !indices.includes(i)){
         return [i, ...indices];
      };
   };
   return -1;
};
console.log(threeSum(arr, 9));
console.log(threeSum(arr, 8));
console.log(threeSum(arr, 13));
console.log(threeSum(arr, 23));

출력

콘솔의 출력은 -

[ 0, 2, 4 ]
[ 0, 2, 3 ]
[ 0, 4, 6 ]
-1