Regular readers of LeetCode will no doubt be aware of the famous twoSum problem, the twoSum problem that was at the heart of our previous article, which analyzed several variations of twoSum.
But in addition to the twoSum problem, LeetCode also has the 3Sum problem, the 4Sum problem, so I’m guessing we’ll have a 5Sum problem in the future, and 6Sum is not out of the question.
So, is there a good way to solve this problem with routines? In this paper, from shallow to deep, layer by layer, with a function to solve all types of nSum problems.
TwoSum question
In the last article, I wrote the twoSum problem on the forcingtwosum. The title required the return of the index. Here I will make up a twoSum problem:
If you take an array of nums and a target and return the values of the two elements in nums that make up the target, for example, nums = [1,3,5,6], target = 9, then the algorithm returns two elements [3,6]. We can assume that only one and only one pair of elements can make target.
We can sort nums first, and then use the left and right two-pointer technique we wrote earlier, from both ends of the line:
vector<int> twoSum(vector<int>& nums, int target) {
// Sort the array first
sort(nums.begin(), nums.end());
// Left and right Pointers
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
// Move the left pointer based on the comparison between sum and target
if (sum < target) {
lo++;
} else if (sum > target) {
hi--;
} else if (sum == target) {
return{nums[lo], nums[hi]}; }}return {};
}
Copy the codeThat will solve the problem, but let’s go ahead and make it a little more general, a little more difficult:
Nums may have multiple pairs of elements whose sum is equal to target. Your algorithm returns all pairs of elements whose sum is target.
The function signature is as follows:
vector<vector<int>> twoSumTarget(vector<int>& nums, int target);
Copy the codeFor example, if nums = [1,3,1,2,2,3] and target = 4, the algorithm will return the result: [[1,3],[2,2]].
For the modified problem, the key difficulty is that there may be multiple pairs of and as target, which cannot be repeated. For example, [1,3] and [3,1] in the above example can be repeated only once.
First, the basic idea is definitely still sort plus double pointer:
vector<vector<int>> twoSumTarget(vector<int>& nums, int target {
// Sort the array first
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int sum = nums[lo] + nums[hi];
// Move the left pointer based on the comparison between sum and target
if (sum < target) lo++;
else if (sum > target) hi--;
else {
res.push_back({lo, hi}); lo++; hi--; }}return res;
}
Copy the codeHowever, this implementation would duplicate the result, such as nums = [1,1,1,2,2,3,3], target = 4, and the result [1,3] would definitely duplicate.
The problem is the if branch of the target condition sum ==. When adding the res once, lo and hi should not change by 1 and should also skip all repeating elements:
So, we can make the following changes to the two-pointer while loop:
while (lo < hi) {
int sum = nums[lo] + nums[hi];
// Record the initial values of indexes LO and hi
int left = nums[lo], right = nums[hi];
if (sum < target) lo++;
else if (sum > target) hi--;
else {
res.push_back({left, right});
// Skip all repeating elements
while (lo < hi && nums[lo] == left) lo++;
while(lo < hi && nums[hi] == right) hi--; }}Copy the codeThis ensures that an answer is added only once, and that duplicate results are skipped to get the correct answer. However, inspired by this idea, the first two if branches can also do a little efficiency optimization, skipping the same elements:
vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
// The numS array must be ordered
sort(nums.begin(), nums.end());
int lo = 0, hi = nums.size() - 1;
vector<vector<int>> res;
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.push_back({left, right});
while (lo < hi && nums[lo] == left) lo++;
while(lo < hi && nums[hi] == right) hi--; }}return res;
}
Copy the codeSo we have a general twoSum function, make sure you understand the logic of this algorithm, and we’ll reuse this function when we solve for 3Sum and 4Sum.
The time complexity of this function is very easy to see, even though there are so many while loops in the two-pointer part, the time complexity is O(NlogN), and the time complexity of sorting is O(NlogN), so this function is O(NlogN).
PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.
2. The 3Sum problem
This is the sum of three numbers in question 15 of li Kou:
Return all possible triples of the three elements neutralized by nums.
vector<vector<int>> threeSum(vector<int>& nums);
Copy the codeSo, let’s generalize the problem again. Instead of just summing the triples of 0, let’s count the triples of target, like the twoSum above, and not allow duplicate results:
vector<vector<int>> threeSum(vector<int>& nums) {
// A triplet summing 0
return threeSumTarget(nums, 0);
}
vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {
// Enter the array nums to return all triples with sum as target
}
Copy the codeHow to solve this problem? It’s easy. I’ll do it all. Now we want to find three numbers that sum is target, so for the first number, what might it be? Every element in nums[I] is possible!
So, once you’ve determined the first number, what can the other two numbers be? For target-nums [I], the twoSum function solves the problem 🤔
We can write the code directly, but we need to modify the twoSum function slightly to reuse it:
/* From nums[start], calculate all binary groups in nums and target */
vector<vector<int>> twoSumTarget(
vector<int>& nums, int start, int target) {
// Change the left pointer to start, otherwise unchanged
int lo = start, hi = nums.size() - 1;
vector<vector<int>> res;
while (lo < hi) {
...
}
return res;
}
/* Computes all triples in the array nums whose sum is target */
vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {
// The array must be sorted
sort(nums.begin(), nums.end());
int n = nums.size(a); vector<vector<int>> res;
// enumerate the first number of threeSum
for (int i = 0; i < n; i++) {
// Calculate twoSum for target-nums [I]
vector<vector<int>>
tuples = twoSumTarget(nums, i + 1, target - nums[i]);
// If there is a binary that satisfies the condition, nums[I] is the resulting triplet
for (vector<int>& tuple : tuples) {
tuple.push_back(nums[i]);
res.push_back(tuple);
}
// Skip the case where the first number is repeated, otherwise the result is repeated
while (i < n - 1 && nums[i] == nums[i + 1]) i++;
}
return res;
}
Copy the codeFor example, nums = [1,1,1,2,3] and target = 6.
The key is that you don’t want the first number to be repeated, and for the next two numbers, our twoSum function that we reuse ensures that they are not repeated. So the code must use a while loop to ensure that the first element in 3Sum is not repeated.
At this point, the 3Sum problem is solved, the time complexity is easy to calculate, the sorting complexity is O(NlogN), the double pointer operation in the twoSumTarget function is O(N), The threeSumTarget function calls twoSumTarget in the for loop so the total time complexity is O(NlogN + N^2) = O(N^2).
PS: I have carefully written more than 100 original articles and brushed 200 force button topics hand by hand, all of which were published in labuladong’s algorithm cheat sheet and updated continuously. Suggested collection, in accordance with the order of my article brush topic, master all kinds of algorithm set to re-enter the sea of questions like a duck in water.
The 4Sum problem
This is the sum of four numbers in question 18 of Li Kou:
The function signature is as follows:
vector<vector<int>> fourSum(vector<int>& nums, int target);
Copy the codeAt this point, 4Sum can be used exactly the same way: enumerating the first number, then calling 3Sum to calculate the remaining three numbers, and finally combining the sum as the target quad.
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// The array needs to be sorted
sort(nums.begin(), nums.end());
int n = nums.size(a); vector<vector<int>> res;
// enumerate the first term of fourSum
for (int i = 0; i < n; i++) {
// Calculate threeSum for target-nums [I]
vector<vector<int>>
triples = threeSumTarget(nums, i + 1, target - nums[i]);
// If there are any triples that satisfy the condition, nums[I] is the resulting quad
for (vector<int>& triple : triples) {
triple.push_back(nums[i]);
res.push_back(triple);
}
// The first term of fourSum cannot be repeated
while (i < n - 1 && nums[i] == nums[i + 1]) i++;
}
return res;
}
/* From nums[start], count all triples in nums with sum as target */
vector<vector<int>>
threeSumTarget(vector<int>& nums, int start, int target) {
int n = nums.size(a); vector<vector<int>> res;
// I start from start, everything else is the same
for (int i = start; i < n; i++) {
...
}
return res;
Copy the codeThe for loop calls threeSumTarget, so the total time is O(N^3).
å››, 100Sum problem?
In LeetCode, 4Sum ends there, but if you think back to writing 3Sum and 4Sum, it actually follows the same pattern. I’m sure you can reuse and solve the 5Sum problem by modifying the 4Sum function a little bit, and then solve the 6Sum problem…
So, what if I asked you to solve the 100Sum problem? In fact, we can observe the above solutions and unify the nSum function:
/* Note: nums must be sorted before calling this function */
vector<vector<int>> nSumTarget(
vector<int>& nums, int n, int start, int target) {
int sz = nums.size(a); vector<vector<int>> res;
// At least 2Sum, and the array size should not be smaller than n
if (n < 2 || sz < n) return res;
// 2Sum is the base case
if (n == 2) {
// Double pointer operation
int lo = start, hi = sz - 1;
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.push_back({left, right});
while (lo < hi && nums[lo] == left) lo++;
while(lo < hi && nums[hi] == right) hi--; }}}else {
// calculate (n-1)Sum recursively when n > 2
for (int i = start; i < sz; i++) {
vector<vector<int>>
sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
for (vector<int>& arr : sub) {
// (n-1)Sum plus nums[I] is nSum
arr.push_back(nums[i]);
res.push_back(arr);
}
while (i < sz - 1 && nums[i] == nums[i + 1]) i++; }}return res;
}
Copy the codeWell, it looks very long, but it’s actually a combination of the twoSum solutions, the two-pointer solution for n == 2, and the recursive call for n > 2 to compute the (n-1)Sum and assemble the answer.
It is important to sort the numS array before calling nSum, because nSum is a recursive function. If the sorting function is called in nSum, the recursive sort will be unnecessary and will be inefficient.
For example, let’s write the 4Sum problem in LeetCode:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
// n is 4, counting from nums[0] and is a quad for target
return nSumTarget(nums, 4.0, target);
}
Copy the codeOr LeetCode’s 3Sum problem, find the triplet target == 0:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
// n = 3, starting with nums[0] and summing triples of 0
return nSumTarget(nums, 3.0.0);
}
Copy the codeSo, if you want to calculate the 100Sum problem, you just call this function and you’re done.
＿＿＿＿＿＿＿＿＿＿＿＿＿
Click on my home page for more quality articles.