哈希表(HashTable)&集合(Set)

242. 有效的字母异位词（easy）

• 为了检查 t 是否是 s的重新排列，我们可以计算两个字符串中每个字母的出现次数并进行比较。因为 S 和 T 都只包含 A-Z 的字母，所以一个简单的 26 位计数器表就足够了。
• 我们需要两个计数器数表进行比较吗？实际上不是，因为我们可以用一个计数器表计算 s 字母的频率，用 t 减少计数器表中的每个字母的计数器，然后检查计数器是否回到零。

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

1. 两数之和(easy)

• 两遍哈希表：空间O(n)时间O(n)
  • 第一次遍历原数组，构建哈希表（以值为键，以索引为值）
  • 第二次遍历原数组，在哈希表中查找键 target - nums[i] ，如果存在则返回两个索引
  • 注意判断两个索引不相等（如果原数组有重复元素时这个方法就不好整）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> num_map;
        vector<int> res;
        map<int,int>::iterator it;
        for(int i=0;i<nums.size();i++)
        {
            num_map[nums[i]] = i;
        }
        for(int i =0;i<nums.size();i++)
        {
            it = num_map.find(target-nums[i]);
            if(it!=num_map.end()&&it->second!=i)
            {
                res = {i,it->second};
                return res;
            }
        }
        return res;
    }
};