このブログの目的は、このタイプの leetcode インタビューの質問 (2Sum、3Sum、4Sum ...K-Sum) のすべての可能なソリューション パターンをリストすることです.

典型的な 2Sum のパターン

🕹問題: 整数の配列 num と整数のターゲットを指定すると、2 つの数値の合計がターゲットになるようなインデックスが返されます.各入力には正確に 1 つの解があり、同じ要素を 2 回使用することはできないと想定できます.任意の順序で回答を返すことができます. 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 から開始し、2 つの隣接する要素の合計がターゲットに等しいかどうかを確認します.

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 つのポインター

2sum II leetcode problem を参照して、配列をソートするときに 2 ポインタ パターンを使用できることに注意してください.これは現在の 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 が与えられた場合、 [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 つのポインターを使用する代わりに 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 内の 3 つの整数を見つけます. 3 つの整数の合計を返します.各入力には 1 つの解があると仮定することができます.

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 と nums[i] + nums[j] + nums[k] < target. の数を見つけます

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[a], nums[b], nums[c], nums[d]] 0 <= a, b, c, d < n 、a 、b 、および c が区別されるように、すべての一意の四重項 d の配列を返します. nums[a] + nums[b] + nums[c] + nums[d] == target 回答は任意の順序で返すことができます.

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;
};