이 블로그는 2Sum, 3Sum, 4Sum ...K-Sum과 같은 유형의 leetcode 인터뷰 질문에 대한 가능한 모든 솔루션 패턴을 나열하는 것을 목표로 합니다.

전형적인 2Sum의 패턴

🕹문제: 정수 배열과 정수 대상이 주어지면 두 숫자의 인덱스를 반환하여 대상을 합산합니다. 각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용하지 않을 수 있습니다. 어떤 순서로든 답변을 반환할 수 있습니다. leetcode link

Example:

Input: nums = [2,7,11,15], target = 9 Output:[0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

무차별 대입

더 빠른 솔루션을 아직 고려하지 않는다면 이중 루프가 가장 먼저 떠오를 수 있다고 생각하십시오.
따라서 외부 for 루프는 인덱스 0에서 시작하고 내부 for 루프는 인덱스 1에서 시작하며 두 인접 요소의 합이 target과 같은지 확인합니다.

var twoSum = function(nums, target) {
  for(let i=0; i<nums.length; i++){
    for(let j=i+1; j<nums.length; j++){
      if(nums[i]+nums[j]===target)
       return [i, j]
    }
  }
  return [-1,-1]
};

해시맵

/* Pattern:

1. Build a hash map which save the difference(target- 
   eachElement in the arry) as key, index as value.
2. Iterate the arrya, to see if the difference(target- 
   eachElement in the arry) is in the hasp map.
   2.1 if the difference existed in the hash map, return index
   2.2 if the difference didn't existed in the hash map, then 
       save the difference to the hash map for future use 
       (update the hash map)
*/


var twoSum = function (nums, target) {
  let seen = new Map();

  for (let i = 0; i < nums.length; i++) {
    let diff = target - nums[i];

    if (seen.has(diff)) return [i, seen.get(diff)];
    seen.set(nums[i], i);
  }
};

2 포인터

배열이 정렬될 때 2-포인터 패턴을 사용할 수 있다는 점에 유의하십시오. 2sum II leetcode problem 을 참조할 수 있습니다. 현재 2sum 문제와 정확히 동일하지만 배열이 정렬됩니다.

var twoSum = function(nums, target) {
  let left = 0;                       //1.scope set
  let right = nums.length -1;         //1.scope set

  while(left < right){                //2.while end condition
    let sum = nums[left]+nums[right]; //3.guess answer
    if(sum === target){               //4.check answer
      return [left,right]
    }else if(sum<target){             //5.adjust scope
      left++  
    }else if(sum>target){
      right--                         //5.adjust scope
    }
  }
  return[-1,-1]
};

3Sum의 패턴

🕹문제: 정수 배열 숫자가 주어지면 [nums[i], nums[j], nums[k] , i != j , i != k , j != k 가 되도록 모든 세 쌍nums[i] + nums[j] + nums[k] == 0 ]을 반환합니다. 솔루션 세트에는 중복 트리플렛이 포함되어서는 안 됩니다.

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

정렬 + 2pointers 사고

우리는 여전히 2개의 포인터를 사용하여 2개의 합을 풀 수 있습니다. 2개의 포인터를 사용하는 대신 3개의 포인터를 사용하고 1개의 포인터가 잠겨 있고 다른 2개의 포인터와 2개의 합을 수행합니다.

/* Pattern:
 1. sorted the array.
 2. lock one pointer, and do 2sum with the other two
*/

 var threeSum = function(nums) {
  let result = [];
  nums.sort((a,b)=>a-b);

  if(nums.length<3) return result;

  for(let i=0; i<nums.length-2; i++ ){
    if(i>0 && nums[i]===nums[i-1]) continue; //skip duplicated
    let low = i+1;                      
    let high = nums.length-1;            

    //nums[i] is pointer1,low is pointer2,high is pointer3
    while(low<high){
           if(nums[i]+nums[low]+nums[high]===0){
          result.push([nums[i],nums[low],nums[high]]);

          while(low<high && nums[low]===nums[low+1]) {
                 low++;                //remove all duplicated
              }   
          while(low<high && nums[high]===nums[high-1]) {
                high--;                //remove all duplicated
          }

              low++;
          high--;
           }else if(nums[i]+nums[low]+nums[high]<0){
          low++;
           }else{
              high--;
           }
     }
  }

  return result;
};

3Sum Closest 패턴

길이가 nums 인 정수 배열 n 과 정수 target 가 주어지면 nums 에서 합이 target 에 가장 가깝도록 정수 세 개를 찾습니다. 세 정수의 합을 반환합니다. 각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있습니다.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2

Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:
Input: nums = [0,0,0], target = 1
Output: 0

/*
  Pattern: based on above sort Array + 2 pointers
  the big difference is while loop's duty changed
*/

var threeSumClosest = function (nums, target) {
  nums.sort((a, b) => a - b);
  let distance = Infinity;
  let sum = 0;

  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; //skip dup

    let low = i + 1;
    let high = nums.length - 1;

    while (low < high) {
        let currSum = nums[i] + nums[low] + nums[high];
        if (Math.abs(currSum - target) < distance) {
          sum = currSum;
          distance = Math.abs(currSum - target);
        }

        (currSum < target) ? low++ : high--;
    }
  }

  return sum;
};

3Sum Smaller의 패턴

n  정수nums  정수target의 배열이 주어지면 i, j, k 조건을 충족하는 0 <= i < j < k < n 인덱스 3중항 수를 찾습니다.

Example:
Input: nums = [-2,0,1,3], target = 2   
Output: 2

Explanation: Because there are two triplets which sums are less than 2: [-2,0,1] [-2,0,3]

/* Pattern: based on above sort Array + 2 pointers */

var threeSumSmaller = function(nums, target) {
  let count=0;
  nums.sort((a,b)=>a-b);

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

       let low = i+1;
       let high = nums.length-1;

       while(low<high){
         let sum = nums[i]+nums[low]+nums[high];
         if(sum<target){
             count+=(high-low)
             low++;
         }else{
            high--;
         }
       }
    }

  return count
};

4Sum의 패턴

🕹문제: n개의 정수 배열이 주어지면 nums[i] + nums[j] + nums[k] < target. [nums[a], nums[b], nums[c], nums[d]] , 0 <= a, b, c, d < n , a , b . c 어떤 순서로든 답변을 반환할 수 있습니다.

Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

/* Pattern:
 1. sorted the array.
 2. lock 2 pointer, and do 2Sum with the other two
*/

var fourSum = function (nums, target) {
  let result = [];
  nums.sort((a, b) => a - b);

  for (let i = 0; i < nums.length - 3; i++) { //lock pointer 1
   if (i > 0 && nums[i] === nums[i - 1]) continue;  //skip dup

    //lock pointer 2
    for (let j = i + 1; j < nums.length - 2; j++) {

      //skip dup
      if (nums[j] === nums[j - 1] && j !== i + 1) continue;

      let low = j + 1;
      let high = nums.length - 1;

      while (low < high) {
        let sum = nums[i] + nums[j] + nums[low] + nums[high];

        if (sum === target) {
          result.push([nums[i],nums[j],nums[low],nums[high]]);
          while (low < high && nums[low] === nums[low + 1]) 
            { low++; }
          while (low < high && nums[high] === nums[high - 1]) 
            { high--; }

          low++;
          high--;
        } else if (sum < target) {
          low++;
        } else {
          high--;
        }
      }
    }
  }

  return result;
};