One, foreword
Unconsciously, nearly two years of big factory algorithm as an important indicator to measure candidates. If the algorithm isn’t up to snuff, a lot of big companies will shut you out. If you want to improve your basic skills or prepare to enter the big factory in the future, then start to wake up and get bald :), let’s start with this algorithm question.
Those of you who have brushed leet-code know that the sum of the two numbers is the first problem to start the algorithm, which is relatively easy. But when it comes to the sum of three numbers, the sum of four numbers and the sum of n numbers, do you have the same idea?
In fact, this kind of problems have a common solution, this article will teach you to find the rules, so that ma Ma never worry about your learning.
In this article, I only illustrate two types of algorithms, and do not introduce other methods temporarily, so that you can learn and memorize. Through this article, you will learn:
- Violence algorithm
- Sorting + double pointer algorithm
- Solve n sum type problems
Suggestion: code after look first, oneself run a code in the article
Second, violence algorithm
【题目1】 the sum of two numbers (difficulty: simple)
> sum of two numbers: https://leetcode-cn.com/problems/two-sum/ Given an array of integers nums and a target value target, find the two ** integers in the array and the target value 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.Copy the codeExample:
Given nums = [2, 7, 11, 15], target = 9Copy the codeMethods:
The simplest is the brute force algorithm.
var twoSum = function(nums, target) { for(let i = 0 ; i<nums.length -1; i++) { for(let j = i+1; j < nums.length; j++) { if(nums[i]+nums[j] === target) { return [i, j]; }}}};Copy the codeA two-layer loop is used. The outer loop computes the difference between the current element and the target, and the inner loop looks for the difference and, if found, returns the subscripts of both elements.
Time complexity: O(n^2).
Ok, so we used the brute force algorithm to figure out the sum of the two numbers. So how do we calculate the sum of three and four numbers? And then we look down.
【题目2】 the sum of three numbers (difficulty: medium)
Sum of three: leetcode-cn.com/problems/3s…
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 meet the criteria and are not duplicated.
Note: Repeated triples cannot be included in the answer.
Example:
A given array nums = [1, 0, 1, 2, 1, 4], meet the requirements of the ternary group collection: [[- 1, 0, 1], [1, 1, 2]]Copy the codeMethods:
According to the analogy of the sum of two number violence algorithm, the sum of three number violence algorithm:
var threeSum = function(nums) {
let res = [];
nums.sort((a, b) => a-b);
for (let i = 0; i < nums.length - 2; i++) {
for (let j = i + 1; j < nums.length - 1; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
res.push([nums[i], nums[j], nums[k]])
}
}
}
}
return res;
}
Copy the codeAbove we use a three-level loop, time complexity: O(n^3). Let’s run and get the following results:
Array.from(new Set(res))
Copy the codeBut this is a two-dimensional array, so it’s a little bit of a problem to undo. So here we use the hash method to remove heavy, small white can first to a simple understanding of heavy:
Function unique(arr) {let tempObj = new Set(); let res = []; for(let i =0; i<arr.length; i++) { if(! tempObj.has(arr[i])) { res.push(arr[i]); tempObj.add(arr[i]); } } return res; } uinque (,1,2 [1]); / / [1, 2] -- -- -- -- -- -- -- -- -- -- - line / / advanced version (multidimensional) function unique (arr) {let res = []; let tempObj = new Set(); for(let i =0; i<arr.length; I ++) {// Let tempStr = arr[I] + ''; if(! tempObj.has(tempStr)) { res.push(arr[i]); tempObj.add(tempStr); } } return res; } // try unique([[1,2],[1,2], 2,3]); / / [[1, 2], 2, 3] unique ([[1] [1, 2], [1] [1, 2], 2, 3]). // [[1,[1,2]], 2, 3] //Copy the codeOk fine, let’s continue! Hash to hash the sum of the preceding three numbers:
Function unique(arr) {let res = []; let tempObj = new Set(); for(let i =0; i<arr.length; I ++) {// Let tempStr = arr[I] + ''; if(! tempObj.has(tempStr)) { res.push(arr[i]); tempObj.add(tempStr); } } return res; } var threeSum = function(nums) { let res = []; nums.sort((a, b) => a-b); for (let i = 0; i < nums.length - 2; i++) { for (let j = i + 1; j < nums.length - 1; j++) { for (let k = j + 1; k < nums.length; k++) { if (nums[i] + nums[j] + nums[k] === 0) { res.push([nums[i], nums[j], nums[k]]) } } } } return unique(res); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- line / / the above method to weight synthesis may appear below you are more "advanced" front-end developer var threeSum = function (nums) {let res = []; + let tempObj = new Set(); nums.sort((a, b) => a-b); for (let i = 0; i < nums.length - 2; i++) { for (let j = i + 1; j < nums.length - 1; j++) { for (let k = j + 1; k < nums.length; k++) { if(nums[i]+nums[j]+nums[k] === 0) { + let tempRes = [nums[i] + nums[j] + nums[k]]; + let tempStr = tempRes + ''; + if (! tempObj.has(temStr)) { + res.push(tempRes); + tempObj.add(tempStr); + } } } } } return res; }Copy the codeWell, now we’re done with the brute force algorithm for adding three numbers! Now let’s do the same for a sum of four numbers.
【题目3】 the sum of four numbers (difficulty: medium)
Sum of four numbers: leetcode-cn.com/problems/4s…
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.
Note: repeated quads cannot be included in the answer.
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 codeMethods:
There is nothing that cannot be solved by violence :), let go of the weight first, get the result first:
var fourSum = function(nums, target) {
let res = [];
nums.sort((a, b) => a-b);
for (let i = 0; i < nums.length - 3; i++) {
for (let j = i + 1; j < nums.length - 2; j++) {
for (let k = j + 1; k < nums.length - 1; k++) {
for(let l = k + 1; l < nums.length; l++){
if(nums[i]+nums[j]+nums[k]+nums[l] === target) {
res.push([nums[i], nums[j], nums[k], nums[l]]);
}
}
}
}
}
return res;
}
Copy the code
Next, go again:
Function unique(arr) {let res = []; let tempObj = new Set(); for(let i =0; i<arr.length; I ++) {// Let tempStr = arr[I] + ''; if(! tempObj.has(tempStr)) { res.push(arr[i]); tempObj.add(tempStr); } } return res; } var fourSum = function(nums, target) { let res = []; nums.sort((a, b) => a-b); for (let i = 0; i < nums.length - 3; i++) { for (let j = i + 1; j < nums.length - 2; j++) { for (let k = j + 1; k < nums.length - 1; k++) { for(let l = k + 1; l < nums.length; l++){ if(nums[i]+nums[j]+nums[k]+nums[l] === target) { res.push([nums[i], nums[j], nums[k], nums[l]]); } } } } } + return unique(res); }Copy the codeThere’s nothing a brute force algorithm can’t solve. What? You said it was over time! Anyway, I kind of know how to do this one.
Is this it? Too low, so let’s talk about advanced development.
Sort + double pointer
What are Pointers?
All array problems, most are using double Pointers to solve the problem.
Double pointer refers to that in the process of traversing an object, two Pointers in the same direction (fast and slow Pointers) or opposite directions (colliding Pointers) are used to scan instead of a single pointer, so as to achieve the corresponding purpose.
In other words, the two-pointer method takes full advantage of the fact that arrays are ordered, thus simplifying operations in some cases.
1. Colliding pointer: in an ordered array, the index pointing to the left is defined as the left pointer, and the index pointing to the right is defined as the right pointer, and then the array is traversed from both ends to the middle.
Colliding arrays apply to ordered arrays, which means that when you encounter a problem with an ordered array, the first thing you should think about is using colliding Pointers.
How fast a pointer, is also a double pointer, but two Pointers from the same side began to iterate through group, the two Pointers, respectively defined as pointer quickly (fast) and slow pointer (missile), two Pointers to different strategy to move, until two pointer values are equal (or other special conditions), such as fast growth two at a time, a missile every time growth.
First understand roughly what is the pointer, if you feel vague, it doesn’t matter, do a few questions will!
Let’s start with the easiest one.
【题目1】 the sum of two numbers (difficulty: simple)
Again, the simple title:
Sum of two numbers: leetcode-cn.com/problems/tw…
Given an array of integers nums and a target value target, find the two integers in the array and the target values and return the array with their subscripts that meet the criteria. (Because this problem is too easy, we will modify the problem slightly to learn the use of double Pointers.)
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.
Example:
Given nums = [2, 7, 11, 15], target = 9Copy the codeMethods:
First, say this sentence three times in your mind:
General array of problems, are basically the use of double Pointers to solve the problem!
General array of problems, are basically the use of double Pointers to solve the problem!
General array of problems, are basically the use of double Pointers to solve the problem!
Yes, this problem is using double Pointers! One pointer points to the element with a smaller value, and one pointer points to the element with a larger value. Pointers to smaller elements are traversed from beginning to end, and Pointers to larger elements are traversed from end to head.
- If two Pointers point to the sum of the elements, sum == target, then the desired result is obtained;
- If sum > target, move the larger element to make sum smaller;
- If sum < target, move the smaller element to make sum larger.
The elements in the array are traversed at most once, and the time complexity is O(N). Only two additional variables are used and the space complexity is O(1).
var twoSum = function(nums, target) { let res = []; nums.sort((a, b) => a - b); // let L = 0; // let R = nums.length-1; While (L < R) {const sum = nums[L] + nums[R]; if(sum === target) { res.push(nums[L]); res.push(nums[R]); break; } else if(sum > target) { R--; } else if(sum < target) { L--; } } return res; }; twoSum([3, 1, 7], 8); / / [1, 7)Copy the codeOK, isn’t that easy to understand. Here we go.
【题目2】 the sum of three numbers (difficulty: medium)
Sum of three: leetcode-cn.com/problems/3s…
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 meet the criteria and are not duplicated.
Note: Repeated triples cannot be included in the answer.
Example:
A given array nums = [1, 0, 1, 2, 1, 4], meet the requirements of the ternary group collection: [[- 1, 0, 1], [1, 1, 2]]Copy the codeMethods:
Or this sentence, in mind: any array of topics, the basic use of double Pointers to solve the problem!
1, Get the original array:
nums.sort((a, b) => a - b);
Copy the code
for(let i = 0; i < len; I ++) {// let L = I + 1; let R = len - 1; }Copy the code
- If sum < 0, the left pointer moves to the right
- If sum > 0, the right pointer moves to the left
The code is as follows:
var threeSum = function (nums) { let res = []; if(nums === null && nums.length < 3) return res; let len = nums.length; nums.sort((a, b) => a - b); For (let I = 0; i < len; i++) { if(nums[i] > 0) break; if(i>0 && nums[i] === nums[i-1]) continue; // let L = I + 1; let R = len - 1; while(L < R) { const sum = nums[i] + nums[L] + nums[R]; if(sum === 0) { res.push([nums[i], nums[L], nums[R]]); while(L < R && nums[L] === nums[L+1]) L++; While (L < R && nums[R] === nums[r-1]) R--; / / to heavy L++; R--; } else if(sum < 0) L++; else if(sum > 0) R--; } } return res; }Copy the codeAnd that’s the way it is, if you know one, all the others are similar. What you need to pay attention to is weight loss. From above we can draw the analogy to the sum of four numbers, and continue!
【题目3】 the sum of four numbers (difficulty: medium)
Sum of four numbers: leetcode-cn.com/problems/4s…
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.
Note: repeated quads cannot be included in the answer.
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 codeMethods:
Sort + double pointer
var fourSum = function (nums, target) { let res = []; let len = nums.length; Nums.sort ((a, b) => a-b); if(len < 4) return res; for(let i = 0; i<len-3; I++) {/ / 2: key to weight the if (I > 0 && nums = = = [I] nums] [I - 1) continue; for(let j = i+1; j<len-2; J++) {/ / 5: key to weight the if (j > I + 1 && nums [j] = = = nums [1]) continue; let L = j + 1; // let R = len-1; While (L<R) {sum = nums[I]+nums[j]+nums[L]+nums[R]; if(sum === target) { res.push([nums[i], nums[j], nums[L], nums[R]]); while(nums[L] === nums[L+1]) L++; While (nums[R] === nums[r-1]) R--; / / to heavy L++; R--; } else if(sum > target) { R--; } else if(sum < target) { L++; } } } } return res; }Copy the codeFour,
Key points: sort, set the left and right Pointers, de-weight. This kind of problem is such, master one of the other are analogues, we brush the algorithm can also be based on type, quality is greater than quantity.
The above.