preface

About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!

Topic describes

Given an array of n integers, nums, and a target, determine if there are four elements a, b, c, and d in NUMS such that a + b + c + d is equal to target. Find all the quads that satisfy the condition and are not duplicate.

Note: Answers may not contain duplicate quads.

Example 1: input: nums = (1, 0, 1, 0, 2, 2], target = 0 output: [[,1,2-2-1], [- 2,0,0,2], [1,0,0,1]]

Example 2: Input: nums = [], target = 0 Output: []

Link: leetcode-cn.com/problems/4s…

Answer key

  1. Brute force solution, four levels of loop, deduplicated, time complexity O(n4)
  2. Double loop followed by double pointer to reduce the time complexity, while sorting in advance for deduplicating, see code, time complexity O(n³)
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[][]}* /
var fourSum = function(nums, target) {
    if (nums.length < 4) return []
    nums.sort((a,b) = > a - b)
    const n = nums.length
    let res = []
    for (let i = 0 ; i < n - 3; ++i) {
      if (i > 0 && nums[i] === nums[i-1]) continue  / / to heavy
      for (let j = i + 1; j < n - 2; ++j) {
        if (j > i + 1 && nums[j] === nums[j-1]) continue / / to heavy
        let l = j + 1
        let r = n - 1
        const leave = target - nums[i] - nums[j]
        while (l < r) {
          if (nums[l] + nums[r] === leave) {
            res.push([nums[i], nums[j], nums[l], nums[r]])
            while (l < r && nums[l] === nums[l+1]) ++l / / to heavy
            while (l < r && nums[r] === nums[r-1]) --r / / to heavy
            ++l
            --r
          } else if (nums[l] + nums[r] > leave) {
            --r
          } else {
            ++l
          }
        }
      }
    }
  return res
};
Copy the code