Reference: a method to solve the nSum problem
In an array, given a targer, find n numbers so that their sum is target
For example, the array is [- 4, - 4, - 3, - 2, - 1,0,1,2,3,4,4]
When n = 2, target=0, the results are [- 4,4], [- 3,3]
When n = 3, target=0, the results are [- 4,1,3], [- 3,1,2]
When n = 4, target=1, the result is [- 4, - 2,3,4]
There are different combinations of subscripts,
You can also ask how many different combinations of array elements there are
Sum of two numbers
The hash table method can be used to solve this problem
Remember that the current element is a and traverse from the beginning,
- If the element target - a does not exist in the hash table, add the element value key and subscript as value to the hash table
- If the element target - a exists in the hash table, it exists. Just return the subscripts of the two elements.
If it is not found at the end of the array, it means that there is no
You can use sorting plus double pointers
First, sort the whole, and then traverse the first and second pointers. The method is similar to binary search.
Difficulty upgrade
In nums, there may be multiple pairs of child elements whose sum is equal to target. Please return all element pairs whose sum is target in your algorithm, and there can be no duplication.
For example, if the input is num = [1,3,1,2,2,3] and target = 4, the result returned by the algorithm is: [[1,3], [2,2]].
For the modified problem, it is not difficult to return the value of the element instead of the corresponding index. The key difficulty is that there may be multiple pairs with a sum of target, which cannot be repeated. For example, in the above example, even if [1,3] and [3,1] are repeated, they can only be counted once.
For the example mentioned above, because you are asking for the value of array elements, you can sort them first
After sorting, [1, 1, 2, 2, 3, 3]
Because it is required that the result set is composed of the same element values only once
Using double pointers, in the traversal process, gradually reduce the distance between the two pointers. If the pointers meet and no new result set is generated, it means that the current element cannot meet the requirements of the topic, then start from the next element.
// Pseudo code
// Sort the array first
sort(nums);
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
// Move the left and right pointers according to the comparison between sum and target
if (sum < target) lo++;
else if (sum > target) hi--;
else {
res.add({lo, hi});
lo++; hi--;
}
}
return res;
}
This will add the set of repeated element values to the result set, so we must find a way to duplicate it in the process of adding the result set.
Either add the result set to remove the duplicate, or remove the duplicate before adding. Write it yourself to know how troublesome it is to remove the duplicate after adding the result. Therefore, it is also a general processing scheme to remove the duplicate reasonably before adding.
Analyze the causes of repeated results and find that,
[1，1，2，2，3，3]，target=4
The problem lies in the if branch of the sum == target condition. After adding a result to res, lo and hi should not only change 1, but should skip all repeated elements
//Pseudo code
while (lo < hi) {
int sum = nums[lo] + nums[hi];
// Record the initial corresponding values of the indexes lo and hi
int left = nums[lo], right = nums[hi];
if (sum < target) lo++;
else if (sum > target) hi--;
else {
res.add({left, right});
// Skip all duplicate elements
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
In this way, you can ensure that an answer is added only once, and the repeated results will be skipped to get the correct answer. However, inspired by this idea, the first two if branches can also do some efficiency optimization and skip the same elements
//Pseudo code
while (lo < hi) {
int sum = nums[lo] + nums[hi];
int left = nums[lo], right = nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] == left) lo++;
} else if (sum > target) {
while (lo < hi && nums[hi] == right) hi--;
} else {
res.add({left, right});
while (lo < hi && nums[lo] == left) lo++;
while (lo < hi && nums[hi] == right) hi--;
}
}
return res;
Sum of three
For the sum of three numbers equal to target, it can be regarded as a given number plus the remaining numbers, and the sum of two numbers is equal to target minus the given number
public List<List<Integer>> threeSum( int[] nums ) {
List<List<Integer>> res = new ArrayList<>();
//Sort first
Arrays.sort( nums );
// Start with each element and find out if there are two corresponding numbers that add up to 0
for ( int i = 0; i < nums.length; i++ ) {
//Special operation when target=0. If the topic is given to target, there is no such step
if ( nums[i] > 0 ) {
return res;
}
//This step is de duplication if the current element is equal to the previous element
// Then, for elements with the same value, if there are two other numbers that meet the requirements of the topic,
///It must be the same as the result set of the previous number
if ( i > 0 && nums[i] == nums[i - 1] ) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while ( right> left ) {
int sum = nums[i] + nums[left] + nums[right];
if ( sum > 0 ) {
right--;
} else if ( sum < 0 ) {
left++;
} else if ( sum == 0 ) {
res.add( Arrays.asList( nums[i], nums[left], nums[right] ) );
while ( right > left && nums[right] == nums[right - 1] ) {
right--;
}
while ( right > left && nums[left] == nums[left + 1] ) {
left++;
}
right--;
left++;
}
}
}
return res;
}
Sum of four numbers
In the same way, four numbers can be simplified to, given a number, find three of the remaining numbers equal to
target - given number
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//If the current number is equal to the previous number, skip because the result set already exists,
//Or it must not exist
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
//The principle of weight removal is the same as above
if (j > i + 1 && nums[j - 1] == nums[j]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (right > left) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
}
return result;
}
summary
In the sum of two numbers, violent method O (n^2)
Use double pointers to increase a limited number of variables to one dimension
In the sum of three, violent method O (n^3)
Change to multiple pointers, add a limited number of variables, and reduce to two dimensions
Of the sum of four, violent method O (n^4)
Change to multiple pointers, add a limited number of variables, and reduce to three-dimensional
It is equivalent to using multiple pointers, which can reduce the original algorithm by one latitude.