LeetCode-哈希问题

Last updated on 8 months ago

这里先填个坑 ： set map 容器底层的原理

1. 有效的字母异位词

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

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

  • s 和 t 仅包含小写字母

思路： 统计s中字符出现的次数，然后再统计 t 中字符出现的次数看是否匹配 ，s和 t 仅仅包含小写字母，所以一小写字母作为key值，出现次数作为 value，出现过的value肯定大于0；再次统计t的，t中出现过的字符对value减一，如果两个字符串出现次数样的话，则map中任何一个value都应为0才对；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isAnagram(string s, string t) {
    int strmap[26] = {0};  //这里我用了一个数组来模拟map
    for (auto ch : s) {
      strmap[ch - 'a']++;
    }
    for (auto ch : t) {
      strmap[ch - 'a']--;
    }
    int sum = 0;
    for (int i = 0; i < 25; i++) {
      if (strmap[i] > 0) return false;
    }

    return true;
  }

2. 两个数组的交集

如题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
    unordered_set<int> num;
    unordered_set<int> res;
    if (nums1.size() == 0 || nums2.size() == 0) {
      return {};
    }
    for(auto n:nums1){
      num.insert(n);
    }
    for(auto n:nums2){
      if(num.find(n) != num.end()){
        res.insert(n);
      }
    }
    return vector<int>(res.begin(),res.end());
  }

3 .两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

思路： 遍历数组 ，查找 target-nums[i] 值有无在数组中（因为数组元素是唯一的），在数组中查找有无匹配的可以使用map

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> twoSum(vector<int> &nums, int target) {
  if (nums.size() == 0) return {};
  unordered_map<int, int> numsmap;   
  for (int i = 0; i < nums.size(); i++) {  
    auto iter = numsmap.find(target-nums[i]);   //要查找的目标
    if(iter == numsmap.end()){ //没有在map中找到
      numsmap.insert(nums[i],i);  //则向map中插入元素
    }
    else{
      return {iter->second,i};   //找到了 则返回坐标
    }
  }
}

3 .三数之和

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

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

思路： 排序 + 双指针 三数之和为 0 ，遍历每一个数，从剩下的数找到符合条件的两位数 ， 题目要求需要去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
vector<vector<int>> threeSum(vector<int> &nums) {
  vector<vector<int>> res;
  if (nums.size() == 0) return res;
   sort(nums.begin(), nums.end());   //排序
  for (int i = 0; i < nums.size() - 1; i++) { //遍历数组每个元素
    int right = nums.size() - 1;
    int left = 0;
    if (nums[i] > 0) {   //因为排序是升序   所以当前数大于0 了，剩下的数也不符合条件了
      return res;
    }
    if (i > 0 && nums[i] == nums[i - 1]) {  //去重 不是第一元素的时候， 看当前的数和前一个数是相同
      continue;
    }
    // 现在已经用了一个数，接下要找到剩下的两位数， 从头和尾各自开始找
    left = i + 1;   
    right = nums.size() - 1;
    while (right > left) {
       //找头和尾的数 看大了还是小了，大了尾往左缩，小了往右缩
      if (nums[i] + nums[left] + nums[right] == 0) {  //符合条件 则加入res中
          
        res.push_back(vector<int>{nums[i], nums[left], nums[right]});
        //此时还去重，如果说两个指针缩短了后，下个数还是一样的，那会有重复的结果
        //首尾都需要去重
        while (left < right && nums[right] == nums[right - 1]) {
          right--;
        }
        while (left < right && nums[left] == nums[left + 1]) {
          left++;
        }
        right--;
        left++; 
      }
      if (nums[i] + nums[left] + nums[right] > 0) {
        right--;
      }
      if (nums[i] + nums[left] + nums[right] < 0) {
        left++;
      }
    }
  }
  return res;
}

3 .四数之和