The introduction

Share a friend interview algorithm problem, this problem is the force buckle on the original problem, or a certain degree of difficulty, but this kind of problem has a simple version, we will from simple to deep, from easy to difficult to analyze the routine of this kind of problem. As follows:

Given an array of integers and a target, find four numbers in the array so that the sum of the four numbers is equal to target. Find all the different qualified quads in the array.

  1. I’m asking for all the eligible quads, not the number of eligible quads or whether there are any eligible quads, so I can naturally think of brute force search, so I’m going to search all the combinations, and then I’m going to filter out the eligible combinations and add them to the result set.

We’re doing 4-tuples here, so we can do 4 for loops, which is a little bit easier to write but I’m not going to write. Another type of search is backtracking, a more elegant search that uses recursion.

  1. Since the nature of backtracking is also a kind of violent search, in order to improve the search efficiency, it is natural to think of pruning (that is, using some conditions to terminate some meaningless search in advance) to improve the efficiency.

Pruning tips:

Since the answer must not contain duplicate quads, a common de-duplication technique is to sort the array elements.Copy the code

The code looks like this:

The backtracking code is basically a template like this, and I’ve commented it out in the code. Since backtracking is not the focus of this article, there is no more explanation.

Two Sum I

Let’s start with a simple 2sum problem, as follows:

The 2sum problem is a classic one. Given an array of integers and a target, find two elements, sum them as target, and return the subscripts of the two elements.

Solution 1: First, as above, you can use two for loops to search all combinations by force. Return the subscripts of the eligible tuples when they are found. The time complexity of this solution is O(n^2^), the space complexity is O(1).

Solution 2: Use hashMap to reduce the time complexity to O(n). The core idea is to use the element of array as the Key and the corresponding subscript of the element as the value. For each element, check whether target-current element is in the Map. If there are two tuples and target in the array, if not, put the current element into the Map.

Two Sum II

Now let’s change 2sum I to find the two numbers, not the subscripts, and again there’s only one answer for each input.

Analysis: Given an integer array nums and target, find two numbers in the array such that the sum of the two numbers is equal to target, return the two numbers.

Again, the above two methods can solve this problem:

The time complexity of the solution is O(n^2^), and the space complexity is O(1). In solution two, we need to iterate over the array, so the time is O(n), and the space is O(n), because in the worst case, we need to store the entire array.

Now we don’t need to return the subscript, is there another solution? Of course, that’s what we’re talking about today: dual Pointers.

Sort the array in ascending order, then use two Pointers: left to the first element, and right to the last element. Sum (nums[left] + nums[right]); sum (nums[left] + nums[right]); sum (target); If sum=target, then both Pointers point to the element we want. The time complexity is O(nlogn) and the space complexity is O(1), since the array of elements is sorted before being iterated. The code is as follows:

Three Sum

So, having introduced the 2sum problem, let’s move on to the 3sum problem. The title is as follows:

Let’s look at the difference between sum and 2sum:

  1. 2sum is the sum of two numbers. 3sum is the sum of three numbers.
  2. 2sum is a target, 3sum is a target.
  3. The answer to 2sum is unique, and the answer to 3sum needs to be de-duplicated.

Analysis: Nothing to say about the difference; Difference two: 0 can be thought of as a special target; The third difference is that you need to redo the general pattern which is sort or hash. We already did 2sum, so how do we convert 3sum to 2sum? So the big idea is that if you fix a number, let’s say a, then the problem becomes, look for two of the remaining elements in the array, the sum of which is target-a, which is 0 minus a. See, when you fix a number, what you’re left with is a 2sum problem.

To get rid of the weight, we can sort the array first. There are two things to note:

  1. When we need to fix a number, if it’s not the first element in the array, and it’s the same as the previous element, we don’t have to go any further;
  2. When we find a set of solutions, we look to see if there are any elements near the left and right Pointers that are equal to them. If there are, we don’t need them either.

To sum up, the code is as follows:

O(n^2^), O(1)

Four Sum

Having looked at the numbers of three, let’s now go back to the original 4sum problem.

Just like the 3sum problem, let’s think about how we can make it into the 3sum problem. If we fix one number, we can make it into the 3sum problem. The only difference with 3sum is that the second layer uses a hash, because when 3sum is changed to 2sum, the fixed 3sum is no longer the first element in the array. So you can’t get rid of it by comparing it to the previous one. The code looks like this:

Time complexity: O(n^3^), space complexity O(n).

N sum problem

If we have an nsum problem, we can solve it by changing the nsum to (n-1)sum, then (n-1)sum to (n-2)sum, and finally 2sum.