/*
 * [18] 四数之和
 */

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
  nums.sort((a, b) => a - b);
  const ans = []
  const len = nums.length;

  for (let a = 0; a < len; a++) {
    const aVal = nums[a];
    if (a > 0 && aVal === nums[a - 1]) continue;
    for (let b = a + 1; b < len; b++) {
      const bVal = nums[b];
      if (b > a + 1 && bVal === nums[b - 1]) continue;
      let c = b + 1, d = len - 1;
      while (c < d) {
        const cVal = nums[c], dVal = nums[d];
        const sum = aVal + bVal + cVal + dVal;
        if (sum === target) {
          ans.push([aVal, bVal, cVal, dVal]);
          while (c < d && nums[c] === nums[c + 1]) {
            c++;
          }
          while (c < d && nums[d] === nums[d - 1]) {
            d--;
          }
          c++;
          d--;
        } else if (sum > target) {
          d--;
        } else {
          c++;
        }
      }
    }
  }
  return ans;
};
console.log(fourSum([2, 2, 2, 2, 2], 8))