🗓️Day 06 – Hashmap
Topics: Hashmap
Problem solved:
#454 - 4Sum II
#383 - ransom Note
#15 - 3Sum

---

🧩Problem solution – 454. 4Sum II

link

💡Problem description

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples(i, j, k, l)such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 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

Example 2:
Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

Constraints:

n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-2 ²⁸ <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2 ²⁸

🧭Thought Process

If we want to get 0, then we need a positive number and a negative number or two 0. But there are 4 arrays. So we can divide them into 2 groups first, using hashmap to record nums1 + nums2[j] and nums3[p] + nums4[q] and the times of its appearing. Traverse one hashmap and find if there is its opposite number in the other hashmap. If there is, multiply these two numbers and add into the result.

💻Code Implementation

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        map<int,int> m1, m2;
        int i = 0,j = 0;
        int s = 0;
        int n = nums1.size();
        for(i = 0;i<n;i++){
            for(j = 0;j<n;j++){
                s = nums1[i]+nums2[j];
                auto it = m1.find(s);
                if(it==m1.end()){
                    m1[s] = 1;
                }else{
                    m1[s]++;
                }
            }
        }
        for(i = 0;i<n;i++){
            for(j = 0;j<n;j++){
                s = nums3[i]+nums4[j];
                auto it = m2.find(s);
                if(it==m2.end()){
                    m2[s] = 1;
                }else{
                    m2[s]++;
                }
            }
        }
        map<int,int>::iterator iter;
        int temp = 0, res = 0;
        for(iter = m1.begin();iter!=m1.end();iter++){
            temp = 0-iter->first;
            auto it = m2.find(temp);
            if(it!=m2.end()){
                res = res+iter->second*it->second;
            }
        }
        return res;

    }
};

⏱️Complexity Analysis

• Time complexity: O(n²)
• Space complexity: O(n²)

🧩Problem solution – 383. Ransom Note

link

💡Problem description

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.

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

Constraints:

1 <= ransomNote.length, magazine.length <= 105
ransomNote and magazine consist of lowercase English letters.

🧭Thought Process

The most important thing is every letter in ransomNote has appeared at least once in magazine. So we can record the letter and its times of appearance in magazine first, using hashmap Then traverse every letter in the ransomNote, if there is no such letter, return false. Or reduce the times of this letter in hashmap.

💻Code Implementation

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int len1 = ransomNote.size();
        int len2 = magazine.size();
        map<char, int> m;
        int i = 0;
        char c = 0;
        for (i = 0; i < len2; i++) {
            c = magazine[i];
            auto it = m.find(c);
            if (it == m.end())
                m[c] = 1;
            else
                m[c]++;
        }
        for (i = 0; i < len1; i++) {
            c = ransomNote[i];
            auto it = m.find(c);
            if (it == m.end())
                return false;
            else {
                m[c]--;
                if (m[c] == 0)
                    m.erase(c);
            }
        }
            return true;

    }
};

⏱️Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(n)

🧩Problem solution – 15. 3Sum

link

💡Problem description

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.

Example 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.

Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 3000
-10 ⁵ <= nums[i] <= 10 ⁵

🧭Thought Process

Well, I’m talking about hashmap in this passage, but I didn’t use hashmap to solve this problem. Because although hashmap can record the number or their sum easily, it’s a little bit difficult to achieve duplicate triplet. So I use three pointers to solve it. Once we have confirmed the first number, it’s easy to transform the problem into two sum problem.

💻Code Implementation

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for (int first = 0; first < n; ++first) {
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int third = n - 1;
            int target = -nums[first];
            for (int second = first + 1; second < n; ++second) {
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    ans.push_back({nums[first], nums[second], nums[third]});
                }
            }
        }
        return ans;
    }
};

⏱️Complexity Analysis

• Time complexity: O(n²)
• Space complexity: O(1)