leetcode-cn.com/problems/4s…

Answer:

  1. If you are not familiar with the sum of three numbers, you can refer to my problem solving problem: 15. The sum of three numbers, JavaScript double loop + double pointer, detailed comments.
  2. With double Pointers, you can find the sum of two numbers in a loop. The specific approach is to use two Pointers from both ends to the middle of the push, each push to calculate the sum of the two numbers, if less than the target value, it means that the left pointer is too small, the left pointer to the right, know that the value changes, again calculate the sum of the two numbers. The same goes for the right pointer.
  3. If the sum of the two numbers equals the target value, the result is recorded. Then move both Pointers in the middle until a new value appears, and repeat steps 2 and 3.
  4. By using two cycles, the first two values of the quad set are found respectively, and the last two values are found by using a double pointer to form the corresponding results.
  5. The general principle of de-duplication is to sort the array so that the same values are sorted together, and as long as the first value has been used, its corresponding result is considered to have been generated, so as long as it passes throughnums[i] === nums[i - 1]Equal values can be excluded.
  6. Test cases to watch out for:
,0,0,0 0 0Copy the code
[5,5,4, - 3,0,0,4, - 2] 4Copy the code
[1, 2, 5, 4, 3,3,3,5] - 11Copy the code
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[][]}* /
var fourSum = function (nums, target) {
  // Sort to ensure that the comparison works properly
  nums.sort((a, b) = > a - b);
  // Store the result
  let result = [];

  for (let i = 0; i < nums.length - 3; i++) {
    // If there are consecutive equal values, all possible solutions corresponding to the first value have been generated in the first loop, and all subsequent values can be skipped
    if (nums[i] === nums[i - 1]) {
      continue;
    }

    // Cache the target of the first level for the next level to recycle
    let firstTarget = target - nums[i];

    for (let j = i + 1; j < nums.length - 2; j++) {
      // If there are consecutive equal values, ensure that the solution of the first value is generated in the current loop, and skip all subsequent values
      if (j > i + 1 && nums[j] === nums[j - 1]) {
        continue;
      }

      // Cache the target of the second level for the next level to recycle
      let secondTarget = firstTarget - nums[j];

      // Use two Pointers, each advancing from the end of the rest of the array to the middle, to find the result that matches the condition
      let k = j + 1;
      let l = nums.length - 1;

      // if k = l, exit the loop
      while (k < l) {
        // Get the sum of the values of k and l
        const sum = nums[k] + nums[l];

        // If sum is less than secondTarget, then nums[k] is too small.
        if (sum < secondTarget) {
          k++;
          while (nums[k] === nums[k - 1]) { k++; }}// If sum is less than secondTarget, then nums[l] is too small.
        if (sum > secondTarget) {
          l--;
          while (nums[l] === nums[l + 1]) { l--; }}// If sum equals secondTarget, the quad is found
        if (sum === secondTarget) {
          // Store the quad into result
          result.push([nums[i], nums[j], nums[k], nums[l]]);

          // To avoid finding duplicate results, move the k and L Pointers until new values are encountered
          k++;
          while (nums[k] === nums[k - 1]) {
            k++;
          }
          l--;
          while (nums[l] === nums[l + 1]) {
            l--;
          }
        }
      }
    }
  }

  return result;
};
Copy the code