An overview of the
TwoSum is the first problem in LeetCode, which you should be familiar with. The question itself is not difficult, and the idea is very simple, but the point is that there are a lot of questions and ideas that have evolved from this question, and there are quite a few details. Today we will see how TwoSum can play with these specific questions and ideas.
Two kinds of thinking
For the TwoSum class, there are generally two big directions, one using Hash and the other using sort, and then using double Pointers to solve the problem. Let’s see:
The first is the Hash table:
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> remainValues = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
if (remainValues.containsKey(target - nums[i])) {
int anotherIndex = remainValues.get(target - nums[i]);
return new int[] {i, anotherIndex};
}
remainValues.put(nums[i], i);
}
return new int[] {-1, -1};
}
Copy the codeThinking is very simple, time array, each access an element, to determine whether the matching element in the Hash table, if in means that we have found the answer, its output can be, if not found, will be the current element in the Hash table, for the back of the element to match, here because the topic request output element in the array of position, So a HashMap is used to store the accessed elements and their corresponding indexes. Let’s look at the spatiotemporal complexity, which is O(n) because we’re using a Hash table, and O(n) because in the worst case, every element in the array is iterated over, so it’s also O(n). In terms of time, this algorithm is definitely optimal, which makes sense, because if you’re looking for pairs in an array, you’re going to have to look at all the numbers in the array.
Sort and double pointer idea:
public int[] twoSum(int[] n, int t) {
if (n == null || n.length == 0) {
return new int[0];
}
Arrays.sort(n);
int[] result = new int[2];
int l = 0, r = n.length - 1;
while (l < r) {
if (n[l] + n[r] == t) {
result[0] = n[l];
result[1] = n[r];
return result;
} else if (n[l] + n[r] < t) {
l++;
} else{ r--; }}return new int[0];
}
Copy the codeAnd the premise of this is that they’re not asking us to print the position of the element in the array, because sorting changes the position of the element in the array, so we’re just going to print the element itself. The idea here is that there are two Pointers at one end and one at the other. Each time, we compare the sum of the two Pointers to the element we are looking for with the target. If the sum is smaller than target, it means that if the left pointer is unchanged, The left pointer plus any element between the left and right pointer will be smaller than target, which means that the left pointer cannot be the answer, so move the left pointer to the right. If it adds up to the target we’re looking for, bigger than target, similar analysis, then you move the right pointer to the left. So let’s look at the time here, because the sorting operation, the time is going to be order NLGN, and for the space complexity, there’s no extra space here, so the space complexity is constant order 1.
Both approaches are covered, and if you have some programming experience, this is not hard to understand. Have you ever wondered what kind of case each of these approaches would be suitable for? Based on the TwoSum problem, consider the following variations:
- What if a problem asks for all possible answers?
- What if the problem asks for all possible answers, and there are duplicate elements in the array?
- What if the problem asks to find pairs smaller/larger than target?
- How do I find a pair where the difference between two numbers is equal to Target?
- Can TwoSum’s approach be extended to TreeSum or more pairs?
Some of the above problems may have occurred to you, and some may not, so let’s take a look at specific examples with the above problems, and skillfully apply the above two methods to the actual problems.
Deformation problem analysis
The title is TwoSum again, but then you need to return all possible cases (no duplicates), and allow duplicate elements in the array.
Analysis of ideas:
The first thing we need to think about is which of the two approaches mentioned above is best. When you analyze the two sums, you will find that both methods work. Unlike the two sums, when you find the answer, you need to keep looking instead of returning, but because there are duplicate elements in the array, you need to consider the mechanism for removing duplicate elements in both methods. In the case of Hash methods, you don’t know if you’ve added the same answer before, so we consider using a collection to store the answer so that the answer is not repeated; For the sorting method, there is a different way of removing weights. After sorting, the same elements will be next to each other. For the elements we have considered before, we just need to skip. Here’s how to implement sorting:
Code implementation:
public List<int[]> twoSum6(int[] nums, int target) {
if (nums == null || nums.length < 2)
return 0;
Arrays.sort(nums);
List<int[]> results = new ArrayList<>();
int left = 0, right = nums.length - 1;
while (left < right) {
int v = nums[left] + nums[right];
if (v == target) {
int[] result = {nums[left], nums[right]};
results.add(result);
left++; right--;
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
while (left < right && nums[left] == nums[left - 1]){ left++; }}else if (v > target) {
right--;
} else{ left++; }}return results;
}
Copy the code
LeetCode 1099. Two Sum Less Than K
Analysis of ideas:
Traditional twosums ask you to find pairs equal to target, but what about pairs greater than or less than target? At this point, the Hash method will have a hard time working, because the Hash table is better suited to the case of equals. If the sum of the elements to which the left and right Pointers point is greater than or equal to target, then we must move the right pointer to the left. Let two elements and as small as possible so that the head and tail pointer to the current element and is less than the target, we need to record the answer at this moment, although not mention this topic, if want to record matching number, not record one answer at this moment, if the left pointer fixed, in addition to the current right Pointers to elements, If there are duplicate elements in the array, then we need to repeat them as before. Of course, for this problem, we can choose the maximum value that satisfies the condition.
Code implementation:
public int twoSumLessThanK(int[] A, int K) {
if (A == null || A.length == 0) {
return -1;
}
Arrays.sort(A);
int l = 0, r = A.length - 1;
int result = Integer.MIN_VALUE;
while (l < r) {
if (A[l] + A[r] >= K) {
r--;
} else{ result = Math.max(result, A[l] + A[r]); l++; }}return result == Integer.MIN_VALUE ? -1 : result;
}
Copy the code
LeetCode 170. Two Sum III – Data structure design
Analysis of ideas:
Lets you implement a data structure that supports “add elements” and “TwoSum”. You need to combine the advantages and disadvantages of the two methods. The first one is the Hash method. If we use this method, we don’t need to worry too much, we just throw the elements into the array, which means that adding elements takes O(1) time. But TwoSum needed an extra O(n) of space to complete; Now, let’s look at sorting, because we want to keep the elements in order, so it takes O(n) time to add elements, but here we don’t need extra space for the TwoSum operation, which is a combination of adding elements and doing the TwoSum operation quite frequently, So the Hash method is better in terms of time.
Code implementation:
private Map<Integer, Integer> elements;
private int MAX_VALUE = Integer.MIN_VALUE;
private int MIN_VALUE = Integer.MAX_VALUE;
/** Initialize your data structure here. */
public TwoSum(a) {
elements = new HashMap<>();
}
/** Add the number to an internal data structure.. * /
public void add(int number) {
elements.put(number, elements.getOrDefault(number, 0) + 1);
MAX_VALUE = Math.max(MAX_VALUE, number);
MIN_VALUE = Math.min(MIN_VALUE, number);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
if (value < 2 * MIN_VALUE || value > 2 * MAX_VALUE) {
return false;
}
for (int i : elements.keySet()) {
if (i * 2 == value && elements.get(i) >= 2) {
return true;
} else if (i * 2! = value && elements.containsKey(value - i)) {return true; }}return false;
}
Copy the code
LeetCode 15. 3Sum
Analysis of ideas:
Summation of three numbers, Hash tables, and sorting ideas are all possible, but in this case it involves de-duplication, and the preferred method is sorting and double-pointers. So it’s kind of intuitive, you take one element, you go to the other two elements, and you turn 3Sum into 2Sum, and I’ve done both of them, so you can see
Code implementation:
// sort + two pointers
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return new ArrayList<>();
}
Arrays.sort(nums);
List<List<Integer>> results = new ArrayList<>();
for (int i = 0; i < nums.length - 2; ++i) {
if((i ! = 0) && (nums[i] == nums[i - 1])) {continue;
}
List<Integer> result = new ArrayList<>();
twoSum(results, nums, i + 1, -nums[i]);
result = null;
}
return results;
}
private void twoSum(List<List<Integer>> results,
int[] nums,
int startIndex,
int target) {
int left = startIndex, right = nums.length - 1;
while (left < right) {
if (nums[left] + nums[right] > target) {
right--;
} else if (nums[left] + nums[right] < target) {
left++;
} else {
List<Integer> result = new ArrayList<>();
result.add(-target);
result.add(nums[left]);
result.add(nums[right]);
results.add(result);
left++; right--;
while ((left < right) && (nums[left - 1] == nums[left])) {
left++;
}
while((right > left) && (nums[right + 1] == nums[right])) { right--; }}}}Copy the code// HashSet
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return new ArrayList<>();
}
Arrays.sort(nums);
Set<List<Integer>> resultsSet = new HashSet<>();
List<List<Integer>> results = new ArrayList<>();
for (int i = 0; i < nums.length - 2; ++i) {
if((i ! =0) && (nums[i - 1] == nums[i])) {
continue;
}
Set<Integer> existedValue = new HashSet<>();
for (int j = i + 1; j < nums.length; ++j) {
if(! existedValue.contains(nums[j])) { existedValue.add(-nums[j] - nums[i]); }else {
List<Integer> result = new ArrayList<>();
Collections.addAll(result, nums[i], -nums[j] - nums[i], nums[j]);
resultsSet.add(result);
}
}
existedValue = null;
}
results.addAll(resultsSet);
return results;
}
Copy the code
Given an array of integers, find three numbers representing the lengths of three sides of a triangle and ask, how many groups of three such numbers can be found to form a triangle?
Sample 1:
Input: [3, 4, 6, 7] output: 3: can is composed of (3, 4, 6), (3, 6, 7), (4, 6, 7)
Example 2:
Input: [4, 4, 4] Output: 4 Explanation: Any three numbers can form a triangle so the answer is C(3, 4) = 4
Analysis of ideas:
We need to choose three sides so that they can form a triangle. Let’s recall what we learned in high school. The condition for three sides to form a triangle is that the sum of any two sides is greater than the third side. No, we can draw the following conclusion
A < b < c && a + b > c => triangleCopy the codeIf we know the size order of the three edges, then we only need to compare them once.
Let’s see if this is a familiar TwoSum variant problem – what if the problem asks for a smaller/larger pair than target? In this case, we choose C from right to left, and use TwoSum to find a and B. Since they only want to output numbers, we can just add them up as we did before
Code implementation:
public int triangleCount(int[] S) {
if (S == null || S.length == 0) {
return 0;
}
Arrays.sort(S);
int result = 0;
for (int i = S.length - 1; i >= 2; --i) {
int l = 0, r = i - 1;
while (l < r) {
if (S[i] < S[l] + S[r]) { // S[i] < S[l] + S[r] && S[i] > S[r] > S[l]
result += r - l; // Add the possible number
r--;
} else{ l++; }}}return result;
}
Copy the code
LeetCode 18. 4Sum
Analysis of ideas:
4Sum works the same way as 3Sum, except that we need to convert it to 3Sum, which is one more choice than 3Sum
Code implementation:
public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums.length < 4) {
return new ArrayList<>();
}
Arrays.sort(nums);
List<List<Integer>> results = new ArrayList<>();
for (int i = 0; i < nums.length - 3; ++i) {
if(i ! =0 && nums[i] == nums[i - 1]) {
continue;
}
List<List<Integer>> subResults = threeSum(nums, i + 1, target - nums[i]);
for(List<Integer> res : subResults) { res.add(nums[i]); results.add(res); }}return results;
}
private List<List<Integer>> threeSum(int[] nums, int start, int target) {
List<List<Integer>> results = new ArrayList<>();
for (int i = start; i < nums.length - 2; ++i) {
if(i ! = start && nums[i] == nums[i -1]) {
continue;
}
List<List<Integer>> res = twoSum(nums, i + 1, target - nums[i]);
for(List<Integer> r : res) { r.add(nums[i]); results.add(r); }}return results;
}
private List<List<Integer>> twoSum(int[] nums, int start, int target) {
List<List<Integer>> results = new ArrayList<>();
int l = start, r = nums.length - 1;
while (l < r) {
if (nums[l] + nums[r] < target) {
l++;
} else if (nums[l] + nums[r] > target) {
r--;
} else {
List<Integer> result = new ArrayList<>();
result.add(nums[l]); result.add(nums[r]);
results.add(result);
r--; l++;
while (l < r && nums[r] == nums[r - 1]) {
r--;
}
while (l < r && nums[l] == nums[l + 1]) { l++; }}}return results;
}
Copy the code
Given a target, find the case where the difference between two numbers is equal to target
Analysis of ideas:
If we use the Hash table approach, for the traditional TwoSum, we find an answer that satisfies the equation:
num1 + num2 = target
Copy the codeIf target-nums is not in the Hash table, the difference between the two numbers will satisfy the equation:
num1 - num2 = target or num2 - num1 = target
Copy the codeIn this case, we need to judge target + num and num – target, which is different and has one more condition than before.
What if we use sort plus double Pointers? In this case, we need to use the same direction double pointer, the two Pointers are moving from left to right, one in front of the other, and compare with target by subtracting the difference between the right pointer and the left pointer. If the right pointer is small, move the right pointer; if the left pointer is large, move the left pointer, equal to, output the answer.
Code implementation:
public int[] twoDiff(int[] n, int t) {
if (n == null || n.length == 0) {
return new int[0];
}
Arrays.sort(n);
int[] result = new int[2];
int l = 0, r = 1;
while (r < n.length) {
if (l == r) {
r++;
}
if (n[r] - n[l] == t) {
result[0] = n[l];
result[1] = n[r];
return result;
} else if (n[r] - n[l] < t) {
r++;
} else{ l++; }}return new int[0];
}
Copy the code
conclusion
So that’s it for TwoSum, and the interesting thing is, TwoSum can be extended not only to three sums, four sums, but it can also be extended to ksums, but we’re going to have to do dynamic programming here, so I’m not going to talk about it here. I hope you found this post helpful.