[21/08/24 KATA NINJA] leetcode #4


4sum




少し遅い様子です.
次は、改善されていないソリューションコードです.

加速xコード

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  let answer = {};
  nums = nums.sort((a, b) => a - b);
  for (let i = 0; i <= nums.length - 4; i++) {
    for (let j = nums.length - 1; j >= i + 3; j--) {
      let k = i + 1;
      let l = j - 1;

      while (k < l) {
        const r = nums[i] + nums[k] + nums[l] + nums[j];

        if (r < target) {
          k++;
        } else {
          if (r === target) {
            

            answer[`${nums[i]},${nums[k]},${nums[l]},${nums[j]}`] = [nums[i],nums[k],nums[l],nums[j]];

            k++;
            l--;
          } else {
            l--;
          }
        }
      }
    }
  }
  return Object.keys(answer).map(key=>answer[key]);
};

アクセラレータコード

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  let answer = {};
  nums = nums.sort((a, b) => a - b);
  let lastI;
    
  for (let i = 0; i <= nums.length - 4; i++) {
    // 이전의 nums[i] 값과 같다면, 건너뛰어도댐 같은 과정을 반복되게 할 뿐임.
    if(lastI === nums[i]) continue;
    let lastJ;  
    for (let j = nums.length - 1; j >= i + 3; j--) {
      // 이전의 nums[j] 값과 같다면, 건너뛰어도댐 같은 과정을 반복되게 할 뿐임.      
      if(nums[j] === lastJ) continue;
      
      let k = i + 1;
      let l = j - 1;
      while (k < l) {
    
          
        
        const r = nums[i] + nums[k] + nums[l] + nums[j];
        if (r < target) {
        lastK = nums[k];
            
          k++;
        } else {
          if (r === target) {
            
            
            answer[`${nums[i]},${nums[k]},${nums[l]},${nums[j]}`] = [nums[i],nums[k],nums[l],nums[j]];
        lastK = nums[k];
        lastL = nums[l]; 
            
            k++;
            l--;
          } else {
        lastL = nums[l]; 
              
            l--;
          }
        }
        
        
      }
    lastJ = nums[j]
    }
    lastI = nums[i];  
  }
  return Object.keys(answer).map(key=>answer[key]);
};

注意しなければならない事実

     while (k < l) {
        while(nums[k] === lastK) {
            k++;

        }
          
        while(nums[l] === lastL) {
            
            l--
 
            
        }
       // 반복문의 조건에 들어가는 변수들을 반복문안에서 늘리거나 줄였으면 조건을 한번더 체킹해주어야함.
        if(k>=l) break;