2022-01-12

字数统计: 2.6k字 | 阅读时长: 11分

哈希表

哈希表可以快速判断一个元素是否出现在集合中。枚举的时间复杂度是O(n), 哈希表的时间复杂度是O(1)。哈希函数即为: 将数据的值映射到哈希表上。

数据的大小是datasize，对应的哈希表的大小是tablesize。

哈希碰撞: 数据中两个值都映射到了哈希函数上。

拉链法: tablesize可以小于datasize, 但是位于表中相同位置的元素需要排成一条链用链表串起来。

线性探测法: 需要保证tablesize大于datasize

哈希表的三种数据结构:
数组, 集合(set), 映射(map)

在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

std::unordered_set底层实现为哈希表，std::set 和std::multiset 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间.

242.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

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

用了哈希的思想

小结: 数组就是简单的哈希表，但是数组的大小可不是无限开辟的

对于索引长度未知，或者是数据对应的索引很稀疏的情况, 用数组就不是很合理了, 这时候可以考虑用set。

349.两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set <int> result; //unordered_set的底层实现是哈希表
        unordered_set <int> nums(nums1.begin(),nums1.end()); //将nums1中不重复的元素放到nums_set中
//        for(int num:nums2) //从nums2的int型数组中依次将值赋值给num，将num带入for语句代码块中执行。
//        {
//            if(nums.find(num) != nums.end())
//            {
//                result.insert(num);
//            }
//        }
          for(int i = 0; i < nums2.size(); i++) //与上面注释掉的方法等效
          {
              int num = nums2[i];
              if(nums.find(num) != nums.end())//find()函数如果找到相等的返回对应的迭代器，如果没找到返回末尾的迭代器,因此这句话的意思就是如果nums这个set中正好有num的话，就把他存在result里，说明两个数组都有这个元素.
              {
                  result.insert(num);
              }
          }
    return vector <int> (result.begin(),result.end());
    }
};

此题使用unordered_set，底层实现是哈希表

for(int num:nums2)
C++ 11的新特性，相当于

for(int i = 0; i < nums2.size(); i++) //与上面注释掉的方法等效
{
  int num = nums2[i];
}

vector的开始和结束对应 num.begin() 和 num.end(); 插入元素用num.pushback(t) (添加一个值为t的元素); num.size()对应num的大小; num.empty()返回一个bool型数据。

unordered_set开始和结束对应 num.begin() 和 num.end(); 插入元素用num.insert(); 寻找元素用num.find(); 如果找到元素就返回对应的迭代器，没有找到就返回num.end;

202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

思路:首先定义一个求和函数用于每次求和，然后进行循环，如果数变成1，则是快乐数，如果不是1，继续循环，这些数都存在unordered_set离，如果后面出现重复的数，则说明有循环，不是快乐数。

class Solution {
public:
    int getSum(int n)
        {
            int sum = 0;
            while(n)
            {
                sum = sum + (n % 10) * (n % 10);
                n = n / 10;
            }
            return sum;
        }

    bool isHappy(int n) {
        unordered_set <int> set;
        while(1)
        {
            int sum = getSum(n);
            if(sum == 1)
            return true;
            else
            {
                if(set.find(sum) != set.end())
                return false;
                else
                {
                    set.insert(sum);
                    n = sum;
                }
            }
        }
    }
};

1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int,int> map; //定义关联数组
        for(int i = 0; i < nums.size(); i++)
        {
            auto iter = map.find(target - nums[i]); //自动推断数据类型, 可以简化代码
            if(iter != map.end())
            {
                return {iter->second , i}; //返回i元素的下标和iter对应的数据下标
            }
            map.insert(pair <int, int> (nums[i], i)); //第一次循环把第一个元素存入map,然后开始在数组里循环, 寻找有没有和map中的元素一样的, 然后返回两个值,前面的是map中的元素的数组下标, 后面的是
        }
        return {};
    }
};

用到了unordered_map数据结构, 先把元素按键值对的关系存到map中, 然后在数组中找有没有和map中元素之和是target的。这种方法的效率非常高。

注意: map.find()是根据iter->first进行寻找的, 因此定义map.insert时nums[i]和i的值的顺序不能换。

454.四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

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

思路：

首先定义一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
最后返回统计值 count 就可以了

总体思路还是很清晰的

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map <int,int> map; //key是a + b; value是a + b出现的次数
        for(int a : nums1)
        {
            for(int b : nums2)
            {
                map[a+b]++;
            }
        }
        int count = 0;
        for(int c : nums3)
        {
            for(int d : nums4)
            {
                if(map.find(0 - c - d) != map.end())
                {
                    count = count + map[0 - c - d];
                }
            }
        }
        return count;
    }
};

注意的几个点: for(int a : nums1)是C++ 11的新语法。

383.赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

与前面的242题很像，也是用数组作为哈希表。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        for(int i = 0; i < magazine.length(); i++)
        {
            record[magazine[i] - 'a']++;
        }
        for(int j = 0; j < ransomNote.length(); j++)
        {
            record[ransomNote[j] - 'a']--;
        }
        for(int k = 0; k < 26; k++)
        {
            if(record[k] < 0)
            return false;
        }
        return true;
    }
};

当需要去重时使用哈希表不合适，十分复杂，使用双指针很不错。

15.三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector <vector <int>> 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(right > left && nums[right] == nums[right - 1])
                right--;
                while(right > left && nums[left] == nums[left + 1])
                left++;
                left++;
                right--;
                }
            }
        } 
        return result;
    }
};

18.四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector <vector <int>> result;
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size(); i++)
        {
            if(i > 0 && nums[i] == nums[i - 1])
            continue;
            for(int j = i + 1; j < nums.size(); j++)
            {
                if(j > i + 1 && nums[j] == nums[j - 1])
                {
                    continue;
                }
                int left = j + 1;
                int right = nums.size() - 1;
                while(right > left)
                {
                    if(nums[i] + nums[j] > target - nums[left] - nums[right])
                    right--;
                    else if (nums[i] + nums[j] < target - nums[left] - nums[right])
                    left++;
                    else
                    {
                        result.push_back(vector<int> {nums[i], nums[j], nums[left], nums[right]});
                        while(left < right && nums[right] == nums[right - 1])
                        right--;
                        while(left < right && nums[left] == nums[left + 1])
                        left++;
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
};

与前面的三数之和类似，只是多了一层循环，然后将求和的值从0变成了target, 也是用双指针的方法。