Hash table concept
A Hash table is a data structure that accesses data stored in memory based on a Key. That is, it accesses records by computing a function on key values that maps the data for the desired query to a location in the table, which speeds up lookups. This mapping function is called a hash function, and the array of records is called a hash table.
For more details, please click here:
1. Sum of two numbers
The title comes from Question No. 1 in LeetCode: Two sums.
Topic describes
Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts.
You can assume that there is only one answer for each type of input. However, you cannot reuse the same elements in this array.
Example:
Given nums = [2, 7, 11, 15], target = 9Copy the codetitle
Use hash tables to solve the problem.
First set up a map container record to record the values and indexes of the elements, and then iterate through nums.
- The temporary variable Complement is used for each traverse to hold the difference between the target value and the current value
- In this traverse, look for record to see if there is a value matching COMPLEMENT. If found, return the index of the value and the value of the current variable, I
- If it is not found, the element is saved in Record with the index value I
Animation description
Code implementation
// 1. Two Sum
// Time complexity: O(n)
// Space complexity: O(n)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int.int> record;
for(int i = 0 ; i < nums.size() ; i ++){
int complement = target - nums[i];
if(record.find(complement) ! = record.end()){int res[] = {i, record[complement]};
return vector<int>(res, res + 2); } record[nums[i]] = i; }}};Copy the code2. The oldest string without repeating characters
The title comes from question 3 on LeetCode: Longest Substring Without Repeating Characters.
Topic describes
Given a string, find the length of the smallest string that does not contain repeating characters.
title
Create a HashMap, establish the mapping between each character and its last occurrence position, then define two variables res and left, where RES is used to record the length of the longest non-repeating substring, left refers to the first position of the starting position of the non-repeating substring. So it’s going to be minus 1 at initialization.
For each character iterated, if it already exists in the HashMap, and if its mapping value is greater than left, then left is updated to the current mapping value, and then the mapping value is updated to the current coordinate I. This ensures that left is always in front of the current boundary. Then when calculating the length of the window, use i-left to update the result RES.
Code implementation
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, left = - 1, n = s.size();
unordered_map<int.int> m;
for (int i = 0; i < n; ++i) {
if (m.count(s[i]) && m[s[i]] > left) {
left = m[s[i]];
}
m[s[i]] = i;
res = max(res, i - left);
}
returnres; }};Copy the codeexpand
This problem can also be addressed using the sliding window concept.
Create a 256-bit integer array freg to map characters to their locations.
Maintain a sliding window, the window is not repeated characters, to maximize the size of the window, the window keeps sliding right.
- (1) If the current traversal character never appears, then directly expand the right boundary;
- (2) If the current traversal character appears, then narrow the window (the left index moves to the right), and then continue to observe the current traversal character;
- (3) Repeat (1) and (2) until the left index can no longer be moved;
- (4) Maintain a result RES, update the result RES with the size of the window every time, and finally return RES to obtain the result.
Animation description
Code implementation
// 3. Longest Substring Without Repeating Characters
// Slide window
O(len(s))
O(len(charset))
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int freq[256] = {0};
int l = 0, r = - 1; // Slide window is s[l...r]
int res = 0;
// complete loop from l == 0; R == -1, the empty window starts
// to l == s.size(); R == s.size()-1 This empty window closes
// Change the window gradually in each loop, maintain freQ, and record if a new optimal value is found in the current window
while(l < s.size()){
if(r + 1 < s.size() && freq[s[r+1= =]]0){
r++;
freq[s[r]]++;
}else { / / r is | | freq [s] [r + 1] = = 1
freq[s[l]]--;
l++;
}
res = max(res, r-l+1);
}
returnres; }};Copy the code3. Sum of three numbers
It comes from question no. 15 in LeetCode: 3Sum.
Topic describes
Given an array nums containing n integers, determine whether there are three elements *a, b, c, * in nums such that a + b + c = 0. Find all the triples that meet the criteria and are not duplicated.
title
They want us to find three numbers that add up to 0, so unless all three numbers are 0, there will always be a negative number and a positive number, so we can start with one number, and then we can go to the other two numbers, and we just have to find two numbers that are the opposite of the number we picked for the first one. We need to enumerate a and B, and store C into map.
Note that no duplicate results can be returned. Such code is O(n^2) in time. Here we can sort the original array and then iterate over the sorted array, so that we can use a double pointer to iterate over all the combinations of two numbers that satisfy the problem in linear time.
Code implementation
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {};
for (int k = 0; k < nums.size(); ++k) {
if (nums[k] > 0) break;
if (k > 0 && nums[k] == nums[k - 1]) continue;
int target = 0 - nums[k];
int i = k + 1, j = nums.size() - 1;
while (i < j) {
if (nums[i] + nums[j] == target) {
res.push_back({nums[k], nums[i], nums[j]});
while (i < j && nums[i] == nums[i + 1]) ++i;
while (i < j && nums[j] == nums[j - 1]) --j;
++i; --j;
} else if (nums[i] + nums[j] < target) ++i;
else--j; }}returnres; }};Copy the code4. Repeated DNA sequences
Repeated DNA Sequences in LeetCode 187.
Topic describes
All DNA is made up of A series of nucleotides abbreviated to A, C, G and T, such as “ACGAATTCCG”. When studying DNA, it can sometimes be very helpful to identify repeated sequences in DNA.
Write a function to find all 10-letter sequences (substrings) in a DNA molecule that occur more than once.
title
First, the ASCII codes of A, C, G, and T are expressed in binary:
A: 0100 0001 C: 0100 0011 G: 0100 0111 T: 0101 0100
By observing that the last three digits of each character are different, we can distinguish the four characters by the last three digits.
If you want to find a sequence of 10 letters long, if you want to divide each character by three digits, you need 30 digits for 10 characters, which is fine on a 32-bit computer.
To extract the last 30 bits, a mask, 0x7ffFFFF (binary means 27 ones), is used to extract the last 27 bits of the whole sequence, and then a 10-letter sequence (30 bits) is shifted three places to the left.
To store the frequency of the substring, a hash table is used.
First when take out the first ten characters, the hash table, and the string frequency mapping, after each shift to the left three replace one character at a time, a new string in the hash table occurrences, if just once before, is deposited in the return value of the current string array and its occurrences plus one, if ever, it is mapped to 1.
The problem solving code
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> res;
if (s.size() <= 10) return res;
int mask = 0x7ffffff, cur = 0;
unordered_map<int.int> m;
for (int i = 0; i < 9; ++i) {
cur = (cur << 3) | (s[i] & 7);
}
for (int i = 9; i < s.size(); ++i) {
cur = ((cur & mask) << 3) | (s[i] & 7);
if (m.count(cur)) {
if (m[cur] == 1) res.push_back(s.substr(i - 9.10));
++m[cur];
} else {
m[cur] = 1; }}returnres; }};Copy the code5. Intersection of two arrays
Intersection of Two Arrays
Topic describes
Given two arrays, write a function to calculate their intersection.
title
Use of the container class set.
- Iterate over NUM1, storing the elements of NUM1 through the set container Record
- Iterate through num2 to find if there are the same elements in the record, if there are, use the set container resultSet for storage
- Convert a resultSet to a vector
Animation description
Code implementation
// Time complexity: O(nlogn)
// Space complexity: O(n)
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> record;
for( int i = 0 ; i < nums1.size() ; i ++ ){
record.insert(nums1[i]);
}
set<int> resultSet;
for( int i = 0 ; i < nums2.size() ; i ++ ){
if(record.find(nums2[i]) != record.end()){
resultSet.insert(nums2[i]);
}
}
vector<int> resultVector;
for(set<int>::iterator iter = resultSet.begin(); iter ! = resultSet.end(); iter ++ ){ resultVector.push_back(*iter); }returnresultVector; }};Copy the code6. Intersection of two arrays II
Intersection of Two Arrays II
Topic describes
Given two arrays, write a function to calculate their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2,2]Copy the codeExample 2:
Input: nums1 =,9,5 [4], nums2 =,4,9,8,4 [9] output: [4, 9]Copy the codetitle
Similar to the intersection of two arrays in the previous problem. It’s just that map is used here.
- Traversal num1, through the map container record store num1 elements and frequency;
- Iterate through num2 to find if there is the same element in the record (the element’s storage frequency is greater than 0), if so, use the Map container resultVector for storage, and the element’s frequency is reduced by one.
Animation description
Code implementation
// Time complexity: O(nlogn)
// Space complexity: O(n)
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
map<int.int> record;
for(int i = 0 ; i < nums1.size() ; i ++){
record[nums1[i]] += 1;
}
vector<int> resultVector;
for(int i = 0 ; i < nums2.size() ; i ++){
if(record[nums2[i]] > 0){ resultVector.push_back(nums2[i]); record[nums2[i]] --; }}returnresultVector; }};Copy the code7. Number of boomerangs
The title comes from Question 447 in LeetCode: Number of Boomerangs.
Topic describes
Given n pairs of different points on the plane, a boomerang is a tuple (I, j, k) represented by points, where the distance between I and j is the same as the distance between I and K (the order of the tuples needs to be considered).
Find the total number of boomerangs. You can assume that n is at most 500, and that the coordinates of all points are in the closed interval [-10000, 10000].
title
N The maximum value is 500, and the time complexity of O(n^2) can be used.
- Walk through all the points, using each point as an anchor point
- Then I iterate over the other points and count how many points are equidistant from the anchor point
- And then we plug in the n(n-1) calculations and add them to the RES
Note:
-
If you have a point A and two points B and C, if ab and AC are equidistant, then there are two ways to arrange them, ABC and ACb;
-
If there are three points B, C, and D that are equidistant from A, then there are six ways to arrange them: ABC, ACb, ACD, ADC, ABD, and adb;
-
If there are n points equidistant from point A, the arrangement is n(n-1);
-
In order to ensure accuracy, open root operation is not carried out in distance calculation.
-
The res value only really increases when n is greater than or equal to 2, because when n=1, the res value increases by 1 * (1-1) = 0.
Animation description
Code implementation
// Time complexity: O(n^2)
// Space complexity: O(n)
class Solution {
public:
int numberOfBoomerangs(vector<pair<int.int>>& points) {
int res = 0;
for( int i = 0 ; i < points.size() ; i ++ ){
// The frequency with which the distance between point I and all other points in the record occurs
unordered_map<int.int> record;
for(int j = 0 ; j < points.size() ; j ++){
if(j ! = i){// Open root is not used to calculate the distance to ensure accuracy
record[dis(points[i], points[j])] += 1; }}for(unordered_map<int.int>::iterator iter = record.begin() ; iter ! = record.end() ; iter ++){ res += (iter->second) * (iter->second -1); }}return res;
}
private:
int dis(const pair<int.int> &pa, const pair<int.int> &pb){
return(pa.first - pb.first) * (pa.first - pb.first) + (pa.second - pb.second) * (pa.second - pb.second); }};Copy the code8. Add four numbers II
The title comes from LeetCode problem no. 454:4Sum II.
Topic describes
Given four arraylists A, B, C, D that contain integers, calculate how many tuples (I, j, k, L) there are such that A[I] + B[j] + C[k] + D[L] = 0.
To keep things simple, all A, B, C, and D have the same length N, and 0 ≤ N ≤ 500. All integers range from -2^28 to 2^ 28-1, and the final result does not exceed 2^ 31-1.
title
Very similar to Two Sum, hash tables are used to solve the problem.
- Find the sum of both A and B, and establish the mapping between the sum of the two numbers and their occurrence frequency in the hash table;
- If you go over any sum of two numbers in C and D, you just have to look at the hash table to see if there’s a negative of the sum of those two numbers.
Animation description
Code implementation
// Time complexity: O(n^2)
// Space complexity: O(n^2)
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int.int> hashtable;
for(int i = 0 ; i < A.size() ; i ++){
for(int j = 0 ; j < B.size() ; j ++){
hashtable[A[i]+B[j]] += 1; }}int res = 0;
for(int i = 0 ; i < C.size() ; i ++){
for(int j = 0 ; j < D.size() ; j ++){
if(hashtable.find(-C[i]-D[j]) ! = hashtable.end()){ res += hashtable[-C[i]-D[j]]; }}}returnres; }};Copy the codeMore content
