哈希表|242.有效的字母异位词 、349. 两个数组的交集、202. 快乐数、1. 两数之和

242.有效的字母异位词

自己审题思路

使用容器记录下字符串每个字母出现的次数

看完代码随想录题解后的收获

1.当遇到需要快速判断一个元素是否出目前集合里的时候，就第一想到哈希法；
2.数组、set、map都是哈希表；
3.容器内元素无序第一使用unordered_set、unordered_map，由于它们底层实现是哈希表，查询>和删减效率高(set、map、mutilset、mutilmap底层实现是红黑树)；当容器内元素要求有序使用>
set、map；当要求容器内元素可重复时，使用multiset、multimap。

使用map实现代码：

class Solution {
public:
    bool isAnagram(string s, string t) {
      unordered_map<char, int> ans;

      for(auto& c : s) {
        ans[c]++;
      }
      for(auto& c : t) {
        ans[c]--;
      }

      for(auto& v : ans) {
        if (v.second != 0) return false;
      }
      return true;
    }
};

使用数组实现代码:

class Solution {
public:
    bool isAnagram(string s, string t) {
        int record[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            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) {
                // record数组如果有的元素不为零0，说明字符串s和t 必定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
};

参考详解

349. 两个数组的交集

自己审题思路

审完题后不是很清晰，没清楚具体要返回什么

看完代码随想录题解后的收获

1、清楚是要返回两个数组重复的元素，并且不思考顺序，并且输出结果是去重的。
2、如果哈希值比较少、特别分散、跨度超级大，使用数组就造成空间的极大浪费！

代码：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

把握什么时候使用数组，什么时候使用set

参考详解

202. 快乐数

自己审题思路

对取数值各个位上的单数操作不熟悉，卡了一会儿。

看完代码随想录题解后的收获

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重大！
使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

代码：

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

问题代码

#include <vector>
#include <string>
#include<iostream>
#include<set>
#include<unordered_set>

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

    bool isHappy(int n) {
        int sum = n;  
        unordered_set<int> ans;
        while(1) {
            int sum = getSum(sum); // 这里在代码运行过程中sum会被重置为0，不提议这么写，也不好理解
            // sum = getSum(sum); // 这样写不会出错
            if (sum == 1) {
                return true;
            }

            if (ans.find(sum) != ans.end()) {
                return false;
            } else {
                ans.insert(sum);
            }
            // n = sum;
        }
    }
};

上述错误，经过debug后发现：循环体外定义int sum = n;后，在循环体内再定义int sum = getSum(sum),编译器会认为这个两个不同的变量（由于它们作用域不同），循环体内的sum每次循环都会被初始化为0（按理来说局部变量未初始化的值是未知的，值为0可能和编译器有关）。

参考详解

1. 两数之和

自己审题思路

返回的是数组的下标，计算需要用到数组中的值，思考使用map

看完代码随想录题解后的收获

使用数组和set来做哈希法的局限。
数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，由于要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value再保存数值所在的下标。

代码：

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 vector<int> {iter->second, i};
            } else {
                map.insert(pair<int, int>(nums[i], i));
                //map[nums[i]] = i;
            }
        }
        return vector<int> {};
    }
};

参考详解

今日感悟：

1、遇到代码问题善用debug
2、哈希法的使用场景：当遇到需要快速判断一个元素是否出目前集合里的时候，就第一想到哈希法；