A summary of hash table related problems from LeetCode with solutions in C++.
Problems:
242. Valid Anagram
349. Intersection of Two Arrays
202. Happy Number
1. Two Sum
454. 4Sum II
383. Ransom Note
15. 3Sum
18. 4Sum
Problem: Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Case 1: Input: s = “anagram”, t = “nagaram”, Output: true
Case 2: Input: s = “rat”, t = “car”, Output: false
Hint:
// C++
class Solution {
public:
bool isAnagram(string s, string t) {
int hashRecord[26] = {0};
for (int i = 0; i < s.size(); i++) {
// Record frequency of each letter in string s
hashRecord[s[i]-'a']++;
}
for (int i = 0; i < t.size(); i++) {
// Deduct frequency of each letter in string t
hashRecord[t[i]-'a']--;
}
for (int i = 0; i < 26; i++) {
if (hashRecord[i] != 0) {
return false;
}
}
return true;
}
};
Related problems
49. Group Anagrams
438. Find All Anagrams in a String
2. 349. Intersection of Two Arrays
Problem: Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
Case 1: Input: nums1 = [1,2,2,1], nums2 = [2,2], Output: [2]
Case 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4], Output: [9,4] or [4,9]
Hint:
// C++
class Solution1 {
public:
// Unordered set method
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for (int num : nums2) {
// The num of nums2 found in nums_set
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
class Solution2 {
public:
// Array method, both nums1 and nums2 are not large size
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
int hash[1001] = {0};
for(int num : nums1) {
hash[num] = 1;
}
for(int num : nums2) {
if(hash[num] == 1) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
Related problems
350. Intersection of Two Arrays II
Problem: Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
(1) Starting with any positive integer, replace the number by the sum of the squares of its digits.
(2) Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
(3) Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Case 1: Input: n = 19, Output: true, Explanation: 12 + 92 = 82, 82 + 22 = 68, 62 + 82 = 100, 12 + 02 + 02 = 1
Case 2: Input: n = 2, Output: false
// C++
class Solution {
public:
// Get the sum of the squares of every digit
int getSumSquare(int n) {
int sumSquare = 0;
while(n) {
sumSquare += (n % 10) * (n % 10);
n /= 10;
}
return sumSquare;
}
bool isHappy(int n) {
unordered_set<int> set;
while(1) {
int sumSquare = getSumSquare(n);
if(sumSquare == 1) {
return true;
}
// Check whether sumSquare is already in the set,
// namely infinite loop, return false
if(set.find(sumSquare) != set.end()) {
return false;
} else {
set.insert(sumSquare);
}
n = sumSquare;
}
}
};
4. 1. Two Sum
Problem: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Case 1: Input: nums = [2,7,11,15], target = 9, Output: [0,1], Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Case 2: Input: nums = [3,2,4], target = 6, Output: [1,2]
Case 3: Input: nums = [3,3], target = 6, Output: [0,1]
Hint:
// C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// key: num, val: index
std::unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
// Traverse current num and find whether there
// is a matched key (target-num) in the map
auto iter = map.find(target - nums[i]);
if (iter != map.end()) {
return {iter->second, i};
}
// There is no matched key (target-num), then
// add this num to map
map.insert(pair<int,int>(nums[i], i));
}
return {};
}
};
5. 454. 4Sum II
Problem: Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:
(1) 0 <= i, j, k, l < n
(2) nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Case 1: Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2], Output: 2,
Explanation: The two tuples are:
1. (0, 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
Case 2: Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0], Output: 1
// C++
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
// key: a+b, val: frequency of a+b
unordered_map<int,int> umap;
for (int a : nums1) {
for (int b : nums2) {
umap[a+b]++;
}
}
// Get numbers of a+b+c+d=0
int count = 0;
for (int c : nums3) {
for (int d : nums4) {
if (umap.find(0-(c+d)) != umap.end()) {
count += umap[0-(c+d)];
}
}
}
return count;
}
};
Problem: Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote.
Case 1: Input: ransomNote = “a”, magazine = “b”, Output: false
Case 2: Input: ransomNote = “aa”, magazine = “ab”, Output: false
Case 3: Input: ransomNote = “aa”, magazine = “aab”, Output: true
// C++
class Solution1 {
public:
// Brute force
// Time complexity: O(n^2)
// Space complexity: O(1)
bool canConstruct(string ransomNote, string magazine) {
for (int i = 0; i < magazine.length(); i++) {
for (int j = 0; j < ransomNote.length(); j++) {
if (magazine[i] == ransomNote[j]) {
// Delete the letter in ransomNote
ransomNote.erase(ransomNote.begin() + j);
break;
}
}
}
// If ransomNote is empty, return true
if (ransomNote.length() == 0) {
return true;
}
return false;
}
};
class Solution2 {
public:
// Hash table method with array
// Time complexity: O(n)
// Space complexity: O(1)
bool canConstruct(string ransomNote, string magazine) {
int record[26] = {0};
// Add
if (ransomNote.size() > magazine.size()) {
return false;
}
for (int i = 0; i < magazine.length(); i++) {
// Record frequency of each letter in magazine string
record[magazine[i]-'a']++;
}
for (int j = 0; j < ransomNote.length(); j++) {
// Traverse ransomNote string with each letter
record[ransomNote[j]-'a']--;
// Check if ransomNote has the related letter
if (record[ransomNote[j]-'a'] < 0) {
return false;
}
}
return true;
}
};
7. 15. 3Sum
Problem: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.
Case 1: Input: nums = [-1,0,1,2,-1,-4], Output: [[-1,-1,2],[-1,0,1]],
Explanation:
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 distinct triplets are [-1,0,1] and [-1,-1,2]
Notice that the order of the output and the order of the triplets does not matter.
Case 2: Input: nums = [0,1,1], Output: [], Explanation: The only possible triplet does not sum up to 0.
Case 3: Input: nums = [0,0,0], Output: [[0,0,0]], Explanation: The only possible triplet sums up to 0.
// C++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
// Find a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.size(); i++) {
// Return if the smallest value > 0
if (nums[i] > 0) {
return result;
}
// Remove redundant a correctly
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// right > left not right >= left for "0, 0, 0" case
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]});
// Remove redundant b and c
while (right > left && nums[right] == nums[right-1]) {right--;}
while (right > left && nums[left] == nums[left+1]) {left++;}
// Update pointers when a solution is found
right--;
left++;
}
}
}
return result;
}
};
8. 18. 4Sum
Problem: Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
(1) 0 <= a, b, c, d < n
(2) a, b, c, and d are distinct
(3) nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Case 1: Input: nums = [1,0,-1,0,-2,2], target = 0, Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Case 2: Input: nums = [2,2,2,2,2], target = 8, Output: [[2,2,2,2]]
// C++
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
// Find a + b + c + d = target
// a = nums[k], b = nums[i], c = nums[left], d = nums[right]
for (int k = 0; k < nums.size(); k++) {
// Trim
if (nums[k] > target && nums[k] >= 0) {
break;
}
// Remove redundant nums[k]
if (k > 0 && nums[k] == nums[k-1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// Trim
if ((nums[k] + nums[i]) > target && nums[k] + nums[i] >= 0) {
break;
}
// Remove redundant nums[i]
if (i > k + 1 && nums[i] == nums[i-1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
// Remove redundant nums[left] and nums[right]
while (right > left && nums[right] == nums[right-1]) {right--;}
while (right > left && nums[left] == nums[left+1]) {left++;}
// Update pointers
right--;
left++;
}
}
}
}
return result;
}
};