1.Sum of Two Numbers
Solving the sum of two numbers is the first question on LeetCode.
One notable part of the title is that the same element in the array cannot be repeated in the answer.
This paper tries to solve with the most direct method, and then optimize the solution process step by step.
Knowledge points: Use of map, unordered_map (find and count, insert) to remove duplicate solutions.
1.1 Violence Law
When you get the title, the first reaction is to solve the problem violently by traversing the array twice.
Walk through the entire array, try to find an array element whose sum is target for each array element nums[i], and then return the corresponding subscript of the array element.
Because it is a double loop, the time complexity of the algorithm is O(n).
Note: The Title requires no repetitive array elements, so the second cycle should start with the element after nums[i], that is, for (int J = I + 1; J < nums.size(); J +)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
# I < nums.size() - 1 is considered to be the last element in the nums array and no element matches it
# The last element may only match the previous element (two elements and target)
# You can also write I < nums.size()
for(int i = 0; i < nums.size() - 1; i++)
{
for(int j = i + 1; j < nums.size(); j++)
{
if(nums[j] == target - nums[i])
return {i,j};
}
}
# If an element with an array element and a target cannot be found, the subscript {-1, -1} is returned
return {-1,-1};
}
};
1.2 hash table
The above algorithm has a high time complexity. Is there any way to optimize it?
Representing array elements with nums[i], finding target - nums[i] in an array is a time-consuming thing.
So is there a data structure lookup operation with less time complexity?
Yes, the time complexity of hash table lookup is O(1).
Create a hash table with nums[i] as key and element subscript i as value.
Find target - nums[i] in the array and write table.find(target - nums[i]), if an element matching nums[i] is found, the subscript {table[target - nums[i], i} is returned. Otherwise, insert the element nums[i], I into the hash table and continue the search.
Now there's another question: How do I make sure nums[i] doesn't match me?
Match (find and target elements) before inserting elements into the hash table.
Here's an example of the data below
Input: nums = [3,3], target = 6 Output:[0,1]
If there is already 3 in the hash table, then the element with target = 6 can be found in the hash table when the array element is 3. The two 3 have different index values. No duplicate array elements can be found in answers that meet the requirements of the title.
Method 1: Using the find function
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> table;
for(int i = 0; i < nums.size(); i++)
{
if(table.find(target - nums[i]) != table.end())
{
return {table[target - nums[i]], i};
}
table[nums[i]] = i;
}
return {};
}
};
Method 2: Implemented by the count function, greater than 0 means that there is an array element whose sum with nums[i] is a target.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> table;
for(int i = 0; i < nums.size(); i++)
{
if(table.count(target - nums[i]) > 0)
{
return {table[target - nums[i]], i};
}
table[nums[i]] = i;
}
return {};
}
};
Fa 3: Two hash es
First put all the elements of the array into the hash table, then look for and target the elements of the array and determine if they are the elements themselves if (it!= res.end() & & res[target - nums[i]]!= i).
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> res;
for(int i = 0; i < nums.size(); i++)
{
res.insert(make_pair(nums[i],i));
}
for(int i = 0; i < nums.size(); i++)
{
auto it = res.find(target - nums[i]);
if(it != res.end() && res[target - nums[i]] != i)
{
return {it->second, i};
}
}
return {};
}
};
2.Sum of Three Numbers
Now let's look at the sum of three numbers.
Direct traversal (violent solution) of this problem is not possible, so try a common method: the two-pointer method.
Points of knowledge: double pointer, use of vector s (sort sort sort, element insertion).
2.1 Double Pointer Method
Sort the arrays before applying the double-pointer method.
Then consider the special case.
If the number of elements in the array is less than three, it means that there is no triple that meets the requirements of the title, so an empty array {} is returned.
When the array element value is greater than 0, that is, all subsequent elements are greater than 0. It is impossible to have a triple that meets the title requirements, so an empty array {} is returned.
Traversing through array elements takes into account the general situation
i is the current array element, and left and right are the left and right pointers to the array.
int left = i + 1; int right = nums.size() - 1;
When nums[i] + nums[left] + nums[right] = 0, i, left, and right are all in the right place.
When nums[i] + nums[left] + nums[right] > 0, the right value is too large, so right--.
When nums[i] + nums[left] + nums[right] < 0, the value of left is too small, so left++.
At this point, the problem of weightlessness should also be considered, as the title requirement cannot include duplicate tuples.
First consider the weighting of array elements
Notice here that you want to write
if(i > 0 && nums[i] == nums[i - 1])
continue;
That is, array elements that have already appeared before will no longer appear in the tuple.
Instead of
// Wrong de-duplication method, will miss -1, -1,2 this case
/*
if (nums[i] == nums[i + 1]) {
continue;
}
Then consider weighting when nums[i] + nums[left] + nums[right] = 0,
RightSearch left to determine nums[right] == nums[right-1]
Left searches to the right, judging nums[left] == nums[left + 1]
When left = right, i, nums[left], nums[right] has only two elements left and cannot form a tuple
while(left < right && nums[right] == nums[right - 1]) right--; while(left < right && nums[left] == nums[left + 1]) left++; // When you find the answer, the two pointers shrink at the same time right--; left++;
The complete code is given below
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// vector<int> temp;
vector<vector<int>> result;
if(nums.size() < 3) return result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] > 0) return result;
if(i > 0 && nums[i] == nums[i - 1])
continue;
int left = i + 1;
int right = nums.size() - 1;
while(left < right)
{
if(nums[i] + nums[left] + nums[right] > 0)
{
right--;
}
else if(nums[i] + nums[left] + nums[right] < 0)
{
left++;
}
else
{
result.push_back(vector<int>{nums[i], nums[left], nums[right]});
while(left < right && nums[right] == nums[right - 1]) right--;
while(left < right && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
};