[5]

If the cover is good, you’ll get a thumbs up. ^ – ^

This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

11. The sum of four numbers (4sum)

The label

• The sorting
• Double pointer
• medium

The title

Leetcode portal

Let’s just open leetCode.

Given an array, we are asked to find all combinations of four numbers that add up to zero. The difficulty in this problem is how to get rid of the repeated solution. It’s the same idea as three numbers.

The basic idea

It’s basically the same as the sum of the three numbers, except that there’s an I in the middle of the three numbers, and the four numbers need two for the two-digit combination.

Writing implement

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[][]}* /
var fourSum = function(nums, target) {
  let [res, len, first, second, left, right, sum] = [[], nums.length, 0.0.0.0.0]
  / / sentence
  if (len < 4) {
      return[]}/ / first order
  nums = nums.sort((a, b) = > a - b)
  // The first pointer is from 0 to len-3.
  // The second one follows the first one, so first + 1
  for (first = 0; first < len - 3; first++) {
    if (first > 0 && nums[first] === nums[first-1]) {
      continue
    }
    for(second = first + 1; second < len - 2; second++) {
      if (second > first+1 && nums[second] === nums[second-1]) {
        continue;
      }
      // The temporary variable records the sum of the first two selected numbers
      let tempSum = nums[first] + nums[second]
      // use a double pointer
      left = second + 1
      right = len - 1
      while (left < right) {
        sum = tempSum + nums[left] + nums[right]
        // And equal to 0 satisfy the condition to enter the result array
        if (sum === target) {
          res.push([nums[first], nums[second], nums[left], nums[right]])
          // Determine whether the left and right bounds are the same as the next position, remove the repeated solution.
          while (left < right && nums[left] === nums[left+1]) {
            left++
          }
          while (left < right && nums[right] === nums[right-1]) {
            right--
          }
          // Move left and right to the next position to find a new solution
          left++
          right--
        } else if (sum > target) {
          Nums [right] is too large and right moves to the left
          right--
        } else {
          left++
        }
      }
    }
  }
  return res
};

let nums = [-2, -1, -1.1.1.2.2], target = 0
console.log(fourSum(nums, target))
Copy the code

Let’s do one on the first of the year.

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me Presious tower shock the reiver monster, I see the pass, the code is not on