Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

Hello everyone, I am quick-frozen fish 🐟, a water front 💦, like the garish 💐, continuous sand sculpture 🌲 Welcome friends to add my wechat: Sudongyuer pull you into the group of my public number: front-end quick-frozen fish progress together, looking forward to growing together with everyone

Preface 🌧 ️

Algorithms are unfamiliar and familiar to the front-end people, and often we don’t value them as much as the back-end engineers do. But in fact, algorithms have an unshakable position for every programmer.

Because the development process is to convert the actual problem into the computer can recognize the instructions, that is, “data structure” said, “design the data structure, in the application of algorithms on the line”.

The quality of writing instructions will directly affect the performance of the program, and instructions are composed of data structure and algorithm, so the design of data structure and algorithm basically determines the quality of the final program.

The title 🦀

18. Sum of four numbers

The difficulty of medium

You are given an array of n integers, nums, and a target value. Find and return a non-repeating quintuple [nums[a], nums[b], nums[c], nums[d]] that meets all of the following conditions:

  • 0 <= a, b, c, d < n
  • a,b,cd Each other is not the same
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You can return the answers in any order.

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]]Copy the code

Example 2:

Input: nums = [2,2,2,2] target = 8 output: [[2,2,2]]Copy the code

Tip:

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

🌵

The sum of four numbers is on the basis of the sum of three numbers, the outermost layer of the for loop on the line ~

  • Double pointer
  • Take the numS array for example, first sort the array, then have a for loop, I starts at index 0, left at I +1, and right at the end of the array.
  • A = nums[I] b = nums[left] c = nums[right]
  • If nums[I] + nums[left] + nums[right] > 0, then the sum of the three digits is large.
  • If nums[I] + nums[left] + nums[right] < 0, then left moves to the right until left meets right.

How to solve the problem 🐂

It’s essentially adding a for loop to the sum of 15 minus three

  • First, sort the array
  • If nums[j] == nums[J-1], it indicates that the number is repeated, which will lead to the result duplication, so it should be skipped
  • Sorted fixed a number of nums [I], about to use pointer to nums at one end of the [I] behind digital respectively nums [L] and nums [R]
  • If nums[I] is greater than target, the sum of the three numbers must not be equal to target, and the loop ends
  • If nums[I] == nums[i-1], the number is repeated and the result is repeated. Skip this step
  • If sum == target, nums[L] == nums[L+1
  • If sum == target, nums[R] == nums[R−1], the result is repeated and should be skipped, R–

Source 🔥

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[][]}* /
var fourSum = function(nums, target) {
    let result = []
    const length = nums.length
    if(! nums || length <4) return result
    nums.sort((a,b) = >a-b);/ / sorting
    for(let j=0; j<length-3; j++){/ / to j
        if(j>0&&nums[j]===nums[j-1]) {continue
        }
    
    for(let i = j+1; i<length-2; i++){// Greater than 0 and greater than 0 can never be equal to 0
        // if(nums[i]>0){
        // break;
        // }
        / / to heavy
        if(i > j+1 && nums[i] === nums[i-1]) {continue;
        }
        let L = i+1;
        let R = length-1;
        while(L<R){
            / / sum
            const sum = nums[j] + nums[i] + nums[L] + nums[R]
            // add result if = 0
            if(sum===target){
                result.push([nums[j],nums[i],nums[L],nums[R]]);
                / / to heavy
                while(L<R && nums[L]===nums[L+1]){
                    L++
                }
                / / to heavy
                while(L<R && nums[R]===nums[R-1]){
                    R--
                }
                L++
                R--
            }
            else if(sum < target){
                L++
            }
            else if(sum > target){
                R--
            }
        }
    }
    }
    return result
}
Copy the code

Time complexity :O(n^2)

Space complexity :O(n)

Conclusion 🌞

There is no shortcut to the algorithm. We can only write and practice more and summarize more. The purpose of this article is actually very simple, which is to urge myself to complete the algorithm practice and summarize and output. I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.