454. Four-number addition II
Given four arrays of integers nums1, nums2, nums3, and nums4 , all of length n, calculate how many tuples (i, j, k, l) can be satisfied:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Example 1:
importation：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
exports：2
account for：
The two tuples are as follows：
1. (0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
Example 2:
Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1
Tip:
n ==
n ==
n ==
n ==
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
Positive solution (hash)
First, define an unordered_map, where key is the sum of a and b, and value is the number of times the sum of a and b occurs.
Iterate through the Big A and Big B arrays, count the sum of the elements of the two arrays, and the number of occurrences, and put them into a map.
Define the int variable count to count the number of times a+b+c+d = 0 occurs.
Iterate through the big C and big D arrays again, and find out if 0-(c+d) occurs in the map, then use count to count the number of occurrences of the value corresponding to the key in the map.
Finally, it returns the count value and that's it;
Upcode (●'◡'●)
class Solution {
public.
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> umap; //key:value of a+b, value:number of occurrences of value of a+b
// Iterate through the big A and big B arrays, counting the sum of the elements of the two arrays and the number of occurrences, and put it into the map
for (int a : A) {
for (int b : B) {
umap[a + b]++;
}
}
int count = 0; // count the number of times a + b + c + d = 0
// Iterate through the big C and big D arrays to find the value of the key in the map if 0-(c+d) occurs in the map, i.e., the number of occurrences.
for (int c : C) {
for (int d : D) {
if ((0 - (c + d)) ! = ()) {
count += umap[0 - (c + d)];
}
}
}
return count; }
}
}; }
ransom note
Given two strings: ransomNote and magazine, determine whether ransomNote can be formed from the characters inside magazine.
Returns true if possible; otherwise returns false.
Each character in magazine can only be used once in ransomNote.
Example 1:
Input: ransomNote = "a", magazine = "b"
Output: false
Example 2:
Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3:
Input: ransomNote = "aa", magazine = "aab"
Output: true
Tip:
1 <= , <= 105
ransomNote and magazine are made up of lowercase letters.
Positive solution (hash)
Since the title says that there are only lowercase letters, then a space-for-time hashing strategy can be used to record the number of times a letter appears in magazine using an array of length 26.
Then ransomNote is used to verify that the array contains all the letters needed by ransomNote.
Still arrays are used in hashing methods.
Some students may want to use the array to do what, all with the map finished, in fact, in the case of this question, the use of map space consumption than the array some of the larger, because the map to maintain the red-black tree or hash table, but also to do the hash function, is time-consuming! The difference can be seen if the amount of data is large. So arrays are more simple, direct and effective!
Upcode (●'◡'●)
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int has[26];
int n=(),m=();
for(int i=0;i<m;i++){
has[magazine[i]-'a']++;
}
for(int i=0;i<n;i++){
has[ransomNote[i]-'a']--;
if(has[ransomNote[i]-'a']<0){
return false;
}
}
return true;
}
};
15. Sum of three numbers
Given an array of integers, determine if there exists a triple [nums[i], nums[j], nums[k]] that satisfies i ! = j, i ! = k and j ! = k and also satisfies nums[i] + nums[j] + nums[k] == 0. Return all triples that sum to 0 and are not duplicates.
Note: Answers may not contain duplicate triples.
Example 1:
importation：nums = [-1,0,1,2,-1,-4]
exports：[[-1,-1,2],[-1,0,1]]
account for：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
The different triples are [-1,0,1] cap (a poem) [-1,-1,2] 。
Note that the order of the output and the order of the triples do not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation : The only possible ternary sum is not 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible ternary sum is 0.
Tip:
3 <= <= 3000
-105 <= nums[i] <= 105
Positive solution (hash)
This question is still slightly difficult ;)
It looks like the addition of the four numbers above, but it's actually quite different;
Two layers of for loops are enough to determine the values of a and b. You can use hashing to determine if 0-(a+b) appears in the array;
This is actually the right idea, but we have a very tricky problem with the question that says you can't contain duplicate triples.
Putting the eligible triples into vectors and then de-weighting them is very time-consuming and can easily time out, and is the source of such a low pass rate on this question.
The process of de-weighting is not well handled, there are a lot of small details
Upcode (●'◡'●)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> output;
sort((), (), less<int>());
int nu1 = nums[0]-1;
auto it1 = ();
for(; it1 != (); it1++){
if(*it1 > 0) break;
if(*it1 == nu1) continue;
nu1 = *it1;
int nu2 = nu1-1;
auto it2 = it1 + 1;
auto it3 = () - 1;
for(; it2 != (); it2++){
if(nu1+(*it2)*2 > 0) break;
if(*it2 == nu2) continue;
nu2 = *it2;
while(nu1 + nu2 + (*it3) > 0)
it3--;
if(it3 > it2 && nu1 + nu2 + (*it3) == 0)
output.push_back({nu1, nu2, (*it3)});
}
}
return output;
}
};
18. Sum of four numbers
You are given an array of n integers, nums, and a target, target. Find and return a quaternion [nums[a], nums[b], nums[c], nums[d]] that satisfies all of the following conditions and is not duplicated (two quaternions are considered to be duplicated if their elements correspond to each other):
0 <= a, b, c, d < n
a, b, c and d are not identical.
nums[a] + nums[b] + nums[c] + nums[d] == target
You can return to the answers in any order.
Example 1:
importation：nums = [1,0,-1,0,-2,2], target = 0
exports：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Tip:
1 <= <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
Positive solution (double pointer)
The sum of four numbers, and 15. the sum of three numbers are along the same lines, both using the double pointer method;
The basic solution is to apply a layer of for loops on top of 15. the sum of three numbers.
But there are a few details to keep in mind, for example:
Don't judge nums[k] > target and return;
The sum of three numbers can be returned by nums[i] > 0, since 0 is already a definite number;
The topic Sum of Four Numbers target is an arbitrary value;
For example: the array is [-4, -3, -2, -1] and target is -10, it can't be skipped because of -4 > -10;
But we can still go ahead and do the pruning, and the logic becomes nums[i] > target && (nums[i] >=0 || target >= 0) and that's it.
15. The double pointer solution for the sum of three numbers is a one level for loop num[i] for the determinant, then within the loop there are left and right subscripts as double pointers to find nums[i] + nums[left] + nums[right] == 0.
The double pointer solution for the sum of four numbers is a two level for loop nums[k] + nums[i] for deterministic values, still within the loop there are left and right subscripts as double pointers to find out the case where nums[k] + nums[i] + nums[left] + nums[right] == target, and the time complexity of the sum of three numbers is O(n2), the time complexity of the sum of four numbers is O(n3) 。
Then by the same token, sums of five numbers, sums of six numbers, etc. use this solution.
For 15. sum of three numbers (opens new window) double pointer method is the original violence O(n)3) of the solution reduces to O(n2) solution, the two-pointer solution for the sum of four numbers is the solution to the otherwise violent O(nThe solution of 4) reduces to O(n3) of the solution.
Upcode (●'◡'●)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort((),());
vector<vector<int>> res;
int n=();
for(int i=0;i<n-3;i++)
{
if(i>0 && nums[i]==nums[i-1]) continue;
if((long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
if((long)nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
int j=i+1;
for(j=i+1;j<n-2;j++)
{
if(j>i+1 && nums[j]==nums[j-1]) continue;
if((long)nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
if((long)nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
int left=j+1;
int right=n-1;
while(left<right)
{
long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];
if(sum<target) left++;
else if(sum>target) right--;
else
{
res.push_back({nums[i],nums[j],nums[left],nums[right]});
while(left<right && nums[left]==nums[left+1])
left++;
left++;
while(left<right && nums[right]==nums[right-1])
right--;
right--;
}
}
}
}
return res;
}
};
It's not easy to write a blog, so please give me some support 8~!