【算法】代码随想录之哈希表（更新中）

文章目录

前言

一、有效的字母异位词（LeetCode--242）

二、两个数组的交集（LeetCode--349）

三、两数之和（LeetCode--1）

四、四数相加II（LeetCode--454）

五、三数之和（LeetCode--15）

六、四数之和（LeetCode--18）

前言

跟随代码随想录，学习哈希表相关的算法题目，记录学习过程中的tips。

一、有效的字母异位词（LeetCode--242）

【1】题目描述：

【2】解决思想：哈希表中记录每个字母的个数。遍历s字符串，遇到一个字母就使哈希表对应位置+1。遍历t字符串，遇到一个字母就使哈希表对应位置-1。最后，遍历哈希表，若存在不等于0的元素则返回false。

【3】C++代码：

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26] = {0};
        for (int i = 0; i < s.length(); ++i) {
            ++hash[s[i] - 'a'];
        }
        for (int i = 0; i < t.length(); ++i) {
            --hash[t[i] - 'a'];
        }
        for (int i = 0; i < 26; ++i) {
            cout << hash[i] << endl;
            if(hash[i] != 0)
                return false;
        }
        return true;
    }
};

【4】时间复杂度：O(N)，对于每个字符串只遍历了一次。

【5】空间复杂度：O(26)，开辟了额外存储26个字母个数的数组。

二、两个数组的交集（LeetCode--349）

【1】题目描述：

【2】解决思想：哈希表法。首先，遍历nums1数组，将所有元素作为first添加到哈希表中，其second为0（若元素重复则不添加）。其次，遍历nums2数组，查找哈希表中是否存在元素，若存在且没有重复添加到ret则添加到目标数组ret中，每次添加完毕后令其值为1（用来标识是否已经添加过）。最后，返回目标数组ret。

【3】C++代码：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> hash;
        vector<int> ret;
        //遍历nums1，将元素添加到哈希表中，值为0
        for (int i = 0; i < nums1.size(); ++i) {
            auto p = hash.find(nums1[i]);
            if (p == hash.end()) {
                hash.insert(make_pair(nums1[i], 0));
            }
        }
        //遍历nums2，若哈希表中存在且不重复则添加到ret中
        for(int i = 0; i < nums2.size(); ++i) {
            auto p = hash.find(nums2[i]);
            if (p != hash.end() && p->second == 0) {
                p->second = 1;
                ret.push_back(nums2[i]);
            }
        }
        return ret;
    }
};

【4】时间复杂度：O(N)，对于每个字符串只遍历了一次。

【5】空间复杂度：O(N)，开辟了额外的哈希表空间。

三、两数之和（LeetCode--1）

【1】题目描述：

【2】解决思想：哈希表法。遍历nums时查找哈希表中是否存在target-nums[i]的元素，若存在返回对应的下标，若不存在则将nums[i]插入哈希表中。

【3】C++代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i) {
            auto p = hash.find(target - nums[i]);
            if (p != hash.end()) {
                return {p->second, i};
            }
            hash.insert(make_pair(nums[i], i));
        }
        return {};
    }
};

【4】时间复杂度：O(N)，只遍历了一次nums数组。

【5】空间复杂度：O(N)，开辟了额外的哈希表空间。

四、四数相加II（LeetCode--454）

【1】题目描述：

【2】解决思想：哈希表法。首先，双循环遍历nums1和nums2，将它们相加的值保存到哈希表的first中且second为1，若它们已经存在于哈希表中则将second++。其次，双循环遍历nums3和nums4，在哈希表中寻找0-(nums3[i]+nums4[j])，若找到则将ret++。最后，返回ret。

【3】C++代码：

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        //遍历数组nums1和nums2，保存相加的值和出现次数
        unordered_map<int, int> hash;
        for (int a : nums1) {
            for (int b : nums2) {
                hash[a + b]++;
            }
        }
        //遍历数组nums3和nums4，查找0-相加的值是否存在于哈希表中
        int ret = 0;
        for (int c : nums3) {
            for (int d : nums4) {
                if (hash.find(0 - c - d) != hash.end()) {
                    ret += hash[0 - c - d];
                }
            }
        }
        return ret;
    }
};

【4】时间复杂度：O(N^2)，采用了双循环遍历。

【5】空间复杂度：O(N^2)，开辟了额外的哈希表空间。

五、三数之和（LeetCode--15）

【1】题目描述：

【2】解决思想：双指针法，而不用哈希表法（哈希表法去重较为麻烦）。首先，对nums进行从小到大的排序，那么当nums[i]大于0时后续就不可能有符合要求的三元组。其次，left指针指向i+1，right指针指向最后一个元素，在i固定时循环判定i、left、right这三个位置的元素之和是否等于0，若为0则添加到结果数组中，若>0说明太大让right--，若<0说明太小让left++。注意：i、left和right这三个位置都要做去重处理。

【3】C++代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        //从小到大排序
        sort(nums.begin(), nums.end());
        //双指针法
        for (int i = 0; i < nums.size(); ++i) {
            //某个元素已经大于0，后续部分中不可能有负数
            if (nums[i] > 0) {
                return ret;
            }
            //nums[i]去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //双指针寻找符合条件的三元组
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] == 0) {//符合
                    ret.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    //找到三元组后对第二、三个元素去重
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    right--;
                    left++;
                } else if (nums[i] + nums[left] + nums[right] > 0) {//大于目标
                    right--;
                } else {//小于目标
                    left++;
                }
            }
        }
        return ret;
    }
};

【4】时间复杂度：O(N^2)，采用了双循环遍历。

【5】空间复杂度：O(1)。

六、四数之和（LeetCode--18）