“This is the third day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”
The sum of three number
I practiced by the sum of the two numbers mentioned above, and I felt ok. I had a little feeling of doing problems.
Today saw the sum of the three numbers of the topic, can’t wait to do it
The sum of three number
Given an array of n integers nums, target, determine if nums contains three elements A, B, and c such that a + b + c = target. Please find all triples that sum to target and do not repeat.
Example:
Input: nums =,12,6,3,9,2,1,7 [5] target = 13 output: [,6,2 [5], [5,1,7], [3,9,1]]
Idea 1
With the sum of the two numbers in the previous paper, the first thought of fixing a value, and then find the sum of the two numbers as the residual value
For example, fix the first number 5 and find the other two numbers that add up to 13 minus 5=8
public static List<List<Integer>> threeSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
// The sum of two numbers
Map<Integer, Integer> data = new HashMap<>();
for (int j = i + 1; j < nums.length; j++) {
int d2 = need - nums[j];
if(data.containsKey(d2)) { result.add(Arrays.asList(nums[i], nums[j], d2)); } data.put(nums[j], j); }}return result;
}
Copy the codeIt can be done this way, but the algorithm complexity is O(n²) and the space complexity is O(n).
At the same time a little hard to rely on the sum of two suspected solution
The disadvantage is that the space complexity is too large, so try to reduce the space complexity to O(1).
Idea 2
In fact, the sum of three numbers has lost the advantage of using hash to quickly locate the number. If the hard disk solution wastes space, you need to build the hash table multiple times
You don’t have to stick to the previous solution at this point
The sorting + double pointer method is adopted
public static List<List<Integer>> threeSum2(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
// Find the remaining two numbers whose sum is need
// Since this is a sorted array, we can use the first and last Pointers to control the size of the sum
for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) {
// If the sum of the two numbers is greater than need, then the right pointer moves to the left, that is, to a smaller direction by k-- the answer is likely to be found
// if the sum of the two numbers is less than need, the left pointer moves to the right, i.e., in the larger direction to move j++
while (j < k && nums[j] + nums[k] > need) {
k--;
}
// The traversal is complete
if (j == k) {
break;
}
// Find the answer that meets the condition
if(nums[j] + nums[k] == need) { result.add(Arrays.asList(nums[i], nums[j], nums[k])); }}}return result;
}
Copy the code- It appears to be a three-level loop, but the moves of the Pointers J and K in each turn add up to n-1 at most, so the overall time complexity of the solution is O (n²).
- Crucially, the solution does not use extra sets (sorting is done directly on the input array), so the space complexity is only O (1).
Another sum of three numbers
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 sum to 0 and are not repeated.
Note: Repeated triples cannot be included in the answer.
Example 1:
Input: nums = [1, 2, 1, 4] output: [[1, 1, 2], [1, 1]] example 2:
Input: nums = [] Output: [] Example 3:
Input: nums = [0]
Train of thought
So this could be viewed as a special version of the sum of the three numbers in the first problem, which is the target=0 version
I’m going to rewrite this with a while loop, but it’s the same idea
public static List<List<Integer>> threeSum2(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
int need = -nums[i];
// Find the remaining two numbers whose sum is need
// Since this is a sorted array, we can use the first and last Pointers to control the size of the sum
int j = i + 1, k = nums.length - 1;
while (j < k) {
// If the sum of the two numbers is greater than need, then the right pointer moves to the left, that is, to a smaller direction by k-- the answer is likely to be found
// if the sum of the two numbers is less than need, the left pointer moves to the right, i.e., in the larger direction to move j++
while (j < k && nums[j] + nums[k] > need) {
k--;
}
// The traversal is complete
if (j == k) {
break;
}
// Find the answer that meets the condition
if(nums[j] + nums[k] == need) { result.add(Arrays.asList(nums[i], nums[j], nums[k])); } j++; }}return result;
}
Copy the codeThe sum of the nearest three numbers
Given an array of n integers nums and a target value target. Identify the three integers in NUMs so that their sum is closest to target. Returns the sum of these three numbers. Assume that there is only one answer for each set of inputs.
Example:
Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The closest sum to target is 2 (-1 + 2 + 1 = 2).
Train of thought
Do the sum of three numbers after the topic saw this topic thought of sorting + double pointer way, try to achieve this idea
It took about ten minutes to write, but I didn’t pass it. I still felt that my thinking was not right
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) {
int nextSum = nums[i] + nums[j] + nums[k];
while (j < k) {
if (Math.abs((target - nextSum)) < Math.abs(target - result)) {
result = nextSum;
}
if (target - nextSum > 0) { k--; }}}}return result;
}
Copy the codeLook at dapeng’s solution, it is so beautiful, clear thinking, logical, interlocking
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
Initiative and / /
int ans = nums[0] + nums[1] + nums[2];
for(int i=0; i<nums.length; i++) {/ / double pointer
int start = i+1, end = nums.length - 1;
while(start < end) {
int sum = nums[start] + nums[end] + nums[i];
if(Math.abs(target - sum) < Math.abs(target - ans))
ans = sum;
if(sum > target)
end--;
else if(sum < target)
start++;
else
returnans; }}return ans;
}
Copy the codesummary
There are still a lot of problems with the double pointer algorithm. When I first saw it, I felt too clever. Now it seems that it can solve a lot of problems.