background
At the beginning of the road of Leetcode from scratch, I encountered a common problem before, the sum of two numbers, and I also went to review the code I wrote a year ago.
The result was unmistakable brute force cracking.
var twoSum = function(nums, target) { var arr=[]; for(var i=0; i<nums.length-1; i++){ for(var j=i+1; j<nums.length; j++){ if(nums[i]+nums[j]==target){ arr.push(... [i,j]); return arr; }}}};Copy the code
Double loop solution, execution time is only more than 11% of the committed record, by the way, I joke, after this push direct return is what operation? Think of two words, green.
So, I think now to solve this problem, though, now I also not necessarily can think the best way to solve the sum of two Numbers, the sum of three Numbers, the sum of number four, but I think again for a year, I return overdo to see me again now to write articles, if also can say the words “I was young”, that I grow up, also should be a good experience.
(PS: I am a vegetable chicken, ideas and ideas may not be satisfied with the bosses, please bear with me ~)
The sum of two Numbers
The title
Given an integer array nums and an integer target value target, find the two integers in the array and the target values and return their array subscripts.
You can assume that there is only one answer for each type of input. However, the same element in an array cannot be used twice. Answers can be returned in any order.
example
Input: nums = [2,7,11,15], target = 9 output: [0,1]Copy the codeTrain of thought
The double loop brute force cracking used before will definitely not work, because the return is a key->value structure, so we can naturally think of using Map to solve this problem.
Before we write the code, note that the logic is clear:
- First, we create a new Map that stores the mapping between keys and values.
- And then we iterate through the array.
- There are two cases of traversal:
- This value, which we’ve seen in the Map before, means that there’s duplicate data in the array, and we decide if twice that value is the target we want. If so, output the corresponding subscript and the loop ends
- If this value does not exist in the Map, then the corresponding subscript is printed and the loop ends. If it does not exist, just store the current value and key in the Map.
code
var twoSum = function(nums, target) { let map = new Map(); for(let i=0; i<nums.length; i++){ if(map.has(nums[i])){ if( 2*nums[i] === target ){ return [map.get(nums[i]) , i]; } }else{ if(map.has(target - nums[i])){ return [map.get(target - nums[i]) , i]; }else{ map.set(nums[i] , i); }}}};Copy the codeThe results of
B: Well, it’s much better than a year ago, but we still need to think about how to further improve operational efficiency.
The sum of three number
The title
Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated.
Note: Repeated triples cannot be included in the answer.
example
Input: nums = [1, 2, 1, 4] output: [[1, 1, 2], [1, 1]] input: nums = [] output: []Copy the codeTrain of thought
Originally my idea is very simple, the problem of the sum of two Numbers already solution, is not the sum of the three number, array, determine A number A, the sum of two Numbers on the remaining part of the array operation, if the return value is the sum of two Numbers method results (B, C), then we can do A splicing, the array directly to (A, B, C) returns with respect to ok.
We found all the triples. I wanted to transform the sum of the above binary numbers and continue to use Map, but I found it difficult to deal with repeated data, so I wanted to find a new solution.
First, there is a wise saying: “hesitancy first, step by step approaching the double pointer”.
This sentence also gave me the train of thought, I say the train of thought below:
- Following the wisdom above, we sort first and get an sorted array.
- And then we iterate through the array
- If nums[I]>0, and because the array is now sorted from smallest to largest, there are no possible triples and the loop ends
- If nums[I] === nums[i-1], the current value is repeated, and repeat triples cannot occur. Continue skips subsequent operations in the loop body
- Now we set Left = I +1; Set Right = length-1, and we loop from L to R with the condition Left
- If nums[I]+nums[Left]+nums[Right]>0, Right moves to the Left
- If nums[I]+nums[Left]+nums[Right]<0, Left moves to the Right
- If nums[I]+nums[Left]+nums[Right]=0, append nums[I],nums[Left],nums[Right]] to result If nums[Left]==nums[Left+1], L++; If nums[Right]===nums[right-1], then Right –.
- Returns the result
code
var threeSum = function(nums) { let length=nums.length; nums.sort((a,b)=>a-b); let res=[]; for(let i=0; i<length; i++){ if(nums[i]>0){ return res; } if(i>0&&nums[i]===nums[i-1]) continue; let Left=i+1; let Right=length-1; while(Left<Right){ if(nums[i]+nums[Left]+nums[Right]==0){ res.push([nums[i],nums[Left],nums[Right]]); while(Left<Right&&nums[Left]==nums[Left+1]){ Left++; } while(Left<Right&&nums[Right]===nums[Right-1]){ Right--; } Left++; Right--; } else if(nums[i]+nums[Left]+nums[Right]>0){ Right--; }else{ Left++; } } } return res };Copy the codeThe results of
The sum of four number
The title
Given an array nums containing n integers and a target value target, determine whether there are four elements a, B, c, and D in nums such that a + b + C + D is equal to target. Find all quaternions that meet the condition and are not duplicated.
example
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. Meet the requirements of the quad sets for: [[- 1, 0, 0, 1], [2, 1, 1, 2], [2, 0, 0, 2]]Copy the codeTrain of thought
At first, MY idea was very simple, this is all the quads that satisfy the case, so I’m just going to iterate one more layer than the sum of three, so I borrowed the sum of three code and changed it a little bit, so I got this code
/** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var threeSum = function(nums, target) { let length=nums.length; let res=[]; for(let i=0; i<length; i++){ if(nums[i]>target&&nums[i]>0){ return res; } if(i>0&&nums[i]===nums[i-1]) continue let Left=i+1 let Right=length-1 while(Left<Right){ if(nums[i]+nums[Left]+nums[Right]==target){ res.push([nums[i],nums[Left],nums[Right]]); while(Left<Right&&nums[Left]==nums[Left+1]){ Left++; } while(Left<Right&&nums[Right]===nums[Right-1]){ Right--; } Left++; Right--; } else if(nums[i]+nums[Left]+nums[Right]>target){ Right--; }else{ Left++; } } } return res }; var fourSum = function(nums, target) { let length=nums.length; nums.sort((a,b)=>a-b); let res=[]; let tempArr = []; for(let i=0; i<length; i++){ if(nums[i]>target&&nums[i]>0){ return res; } if(i>0&&nums[i]===nums[i-1]) continue tempArr = threeSum(nums.slice(i+1),target-nums[i]); if(tempArr.length>0){ for(let item of tempArr){ res.push([nums[i],...item]); } } } return res; }Copy the codeI’m sure it didn’t work out too well.
So I started rewriting the code, instead of using the sum of the previous three numbers, to sort out my thoughts (the code is parsed line by line) :
- First, we still need to sort the array.
- Because there are four numbers, I use the double loop (first, second) + double pointer traversal (Left, Right) scheme, the time complexity is controlled in O(n3).
- If nums[first]>target&&nums[first]>0, we return. Return the result. First >0&&nums[first]===nums[first-1]
- If nums[first]+nums[second]>target&&nums[second]>0, we break the loop because the array is sorted from smallest to largest. Second >first+1&&nums[second]===nums[second-1]
- The following double pointer traversal, the idea and the sum of the previous three numbers, but the conditions have a little change.
- We set Left = second+1, Right = length-1. The end condition of the double pointer traversal is still Left
- Nums [first]+nums[second]+nums[Left]+nums[Right]>target
- If nums[first]+nums[second]+nums[Left]+nums[Right]
- If nums[first]+nums[second]+nums[Left]+nums[Right]=0,nums[Left] +nums[Right]=0 If nums[Left]==nums[Left+1], L++; If nums[Right]===nums[right-1], then Right –.
- End of the program
code
/** * @param {number[]} nums * @param {number} target * @return {number[][]} */ var fourSum = function(nums,target){ let length=nums.length; nums.sort((a,b)=>a-b); let res = []; let sumTemp = 0; for(let first=0; first<length-3; first++){ if(nums[first]>target&&nums[first]>0){ return res; } if(first>0&&nums[first]===nums[first-1]){ continue; } for(let second=first+1; second<length-2; second++){ if(nums[first]+nums[second]>target&&nums[second]>0){ break; } if(second>first+1&&nums[second]===nums[second-1]){ continue; } let Left=second+1; let Right=length-1; while(Left<Right){ sumTemp = nums[first]+nums[second]+nums[Left]+nums[Right]; if(sumTemp===target){ res.push([nums[first],nums[second],nums[Left],nums[Right]]); while(Left<Right&&nums[Left]===nums[Left+1]){ Left++; } while(Left<Right&&nums[Right]===nums[Right-1]){ Right--; } Left++; Right--; } else if(sumTemp>target){ Right--; }else{ Left++; } } } } return res; }Copy the codeThe results of
(PS: It’s usually about 80%, 90% luck)
conclusion
The sum of two numbers, three numbers and four numbers is still a common problem. Unified sorting has been done here, and the running result is acceptable. The overall idea is double pointer traversal (Map is used for the sum of two numbers).
Of course, I also hope that a year later I will look at my previous thoughts, and joke, “I was really green a year ago”, so. Ha ha