Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of how C++ realizes the sum of four numbers. The content is detailed and easy to understand, the operation is simple and fast, and it has a certain reference value. I believe you will gain something after reading this C++ article on how to achieve the sum of four digits. Let's take a look.

The sum of 4Sum's four numbers

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

Elements in a quadruplet (a _ d _ must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)

The solution set must not contain duplicate quadruplets.

For example, given array S = {10-10-22}, and target = 0.

A solution set is:

(- 1,0,0,1)

(- 2,-1, 1, 2)

(- 2, 0, 0, 2)

LeetCode on the sum of numbers there are several other, respectively, Two Sum, 3Sum, 3Sum Closest, although the difficulty is increasing, but the overall routines are the same, here in order to avoid duplicates, we use the TreeSet in STL, its characteristic is that there can be no repetition, if the newly added number already exists in the TreeSet, the insertion operation will fail, so it can well avoid the existence of duplicates. The O (n ^ 3) solution of this problem is basically the same as that of 3Sum, except that an extra layer of for loop is added, and the other ones are the same. The code is as follows:

Solution 1:

Class Solution {public: vector fourSum (vector & nums, int target) {set res; sort (nums.begin (), nums.end ()); for (int I = 0; I

< int(nums.size() - 3); ++i) { for (int j = i + 1; j < int(nums.size() - 2); ++j) { if (j >

I + 1 & & nums [j] = = nums [j-1]) continue; int left = j + 1, right = nums.size ()-1; while (left)

< right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { vector out{nums[i], nums[j], nums[left], nums[right]}; res.insert(out); ++left; --right; } else if (sum < target) ++left; else --right; } } } return vector(res.begin(), res.end()); }}; 但是毕竟用 TreeSet 来进行去重复的处理还是有些取巧，可能在 Java 中就不能这么做，那么还是来看一种比较正统的做法吧，手动进行去重复处理。主要可以进行的有三个地方，首先在两个 for 循环下可以各放一个，因为一旦当前的数字跟上面处理过的数字相同了，那么找下来肯定还是重复的。之后就是当 sum 等于 target 的时候了，在将四个数字加入结果 res 之后，left 和 right 都需要去重复处理，分别像各自的方面遍历即可，参见代码如下： 解法二： class Solution {public: vector fourSum(vector &nums, int target) { vector res; int n = nums.size(); sort(nums.begin(), nums.end()); for (int i = 0; i < n - 3; ++i) { if (i >

0 & & nums [I] = = nums [I-1]) continue; for (int j = I + 1; j

< n - 2; ++j) { if (j >

I + 1 & & nums [j] = = nums [j-1]) continue; int left = j + 1, right = n-1; while (left < right) {int sum = nums [I] + nums [j] + nums [left] + nums [right] If (sum = = target) {vector out {nums [I], nums [j], nums [left], nums [right]}; res.push_back (out); while (left < right & & nums [left] = = nums [left + 1]) + + left While (left < right & & nums [right] = = nums [right-1])-right; + + left;-- right;} else if (sum < target) + + left; else-- right;} return res;}} This is the end of the article on "how C++ can achieve the sum of four numbers". Thank you for reading! I believe you all have a certain understanding of the knowledge of "how C++ can achieve the sum of four numbers". If you want to learn more knowledge, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.