LeetCode 242.有效的字母异位词

题目链接：LeetCode 242.有效字母异位词

哈希法：

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

思路：设定一个大小为26的数组alphabet；之后分别用两个for循环通过+、-记录每一个字符出现的次数。最后检测每一个数组元素的值是否为0，若都为0则两个字符串互为异位词。

小结：

1.用数组实现哈希法的条件：哈希值较小且范围可控（连续）。

2.在数组alphabet中，将小写字母a的下标设置为0，小写字母z 的下标设置为25；则0~25可以包括所有字母。而要想找到这些字母的位置不需要记住其ASCII码的值，通过s[ i ] – ‘a’便可以通过下标找到对应字母。

改进：

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

思路：因字母异位词必须是长度相同的词，故可以先判断字符串长度是否相同，之后通过一个for循环便可以完成记数。

LeetCode 349. 两个数组的交集

题目链接：LeetCode 349.两个数组的交集

Set:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        unordered_set<int> nums_set(nums1.begin(),nums1.end());
        for(int num:nums2)
        {
            if(nums_set.find(num) != nums_set.end())
            {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(),result_set.end());
    }
};

思路： 将第一个数组nums1转化为哈希表中，在从哈希表中查找第二个数组的元素，如果第一个数组中含第二个数组的元素，则将其存入result_set中，最后以数组的形式返回result_set值。

小结：

1.使用set实现哈希法条件为：哈希值过大,元素范围不可控（不连续）。

2.因题目要求答案需要去重，故使用unordered_set来存储交集元素，最后将其转化为数组返回即可。

3.其中for（int num:num2）为for循环的简化写法即

int num = 0;
for(int i = 0;i < nums2.size();i++)
{
  num = nums2[i];
}

4.nums_set.end ( )为指向该容器最后元素的迭代器；函数find的返回值为指向键等于key的元素的迭代器。若找不到这种元素，则返回 end（）迭代器。

Array：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        int nums[1001] = { 0 };
        for(int num:nums1)
        {
            nums[num]++;
        }
        for(int num:nums2)
        {
            if(nums[num])
            {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(),result_set.end());
    }
};

思路：用数组来存储元素，大体思路与Set写法一致。先记录数组1的元素（非0），若数组2中也存在该元素，即非0，将该元素存入result_set中。

小结：这道题之所以可以用数组，是因为题目规定了nums1和nums2的长度。当长度未知时用set，长度已知时，用array更优。

LeetCode 202. 快乐数

题目链接：LeetCode 202.快乐数

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;
            }
            if(set.find(sum) != set.end())
            {
                return false;
            }
            else
            {
                set.insert(sum);
            }
            n = sum;
        }

    }
};

思路：因题目中需要计算各个位数的平方和，因此我们定义一个函数getSum来得到某个数的平方和。而是否为快乐数一共有两种情况，第一种是多次重复该过程使最终各个位数的平方和为1，第二种是陷入无限循环。因重复次数未知，我们设定一个set，将每一次得到的和存入set中，如果发现和重复，则为无限循环停止该过程，否则就一直循环直到和为1.

小结：

1.求和过程比较巧妙的利用了函数解决。

2.因存在sum重复为无限循环，故利用set哈希法来查找元素是否重复。

LeetCode 1. 两数之和

题目链接：LeetCode 1.两数之和

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};//用于获取map中的value值，即元素下标
            }
            map.insert(pair<int,int>(nums[i],i));//用于存储元素值及其下标
        }
        return {};
    }
};

思路：要找出数组中相加为目标值的两个数，只需要找到1个数与目标值减去该数是否在数组即可。因此本质上属于找重复元素的过程，故使用哈希法。先设定一个map，通过遍历将数组中的数及其下标存入map中，若在之后的遍历中存在目标值减去该数，则返回这两个数的下标。

小结：

因寻找元素为元素的值，而返回值为下标数组，故用map结构的哈希表。其作用为判断某元素是否在遍历中出现过。