数组表示Hash表

数组就是简单的哈希表，但是数组的大小可不是无限开辟的。
要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。但是，使用set和map在有些时候比一定比数组快。例如：要求只有小写字母，此时数组就可以考虑使用。

有效的字母异位词：

题目描述：

力扣链接🔗

题目分析：

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。需要定义一个多大的数组呢，定一个数组叫做record，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

代码：

class Solution {
    public boolean isAnagram(String s, String t) {
        // 暴力解法，两个for循环遍历即可
        // 哈希表（使用数组）
        char[] chars = new char[26];  // 26个字母需要26个空间即可
        // 遍历字符串s
        for (int i = 0; i < s.length(); i++) {
            // 映射在数组中
            chars[s.charAt(i) - 'a']++;
        }
        // 遍历字符串t
        for (int i = 0; i < t.length(); i++) {
            // 映射在数组中
            chars[t.charAt(i) - 'a']--;
        }
        // 最后遍历判断chars数组，存在不为0的返回false
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

赎金信：

题目描述：

力扣链接🔗

题目分析：

与上题一致思路，将字符映射在数组中，在遍历另一个字符串，注意此题需要判断数组中是否存在，再将次数减一。

• 第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。
• 第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要。

代码：

public boolean canConstruct(String ransomNote, String magazine) {
    char[] record = new char[26];
    for (int i = 0; i < magazine.length(); i++) {
        // 通过recode数据记录 magazine里各个字符出现次数
        record[magazine.charAt(i) - 'a']++;
    }
    // 遍历ransomNote
    for (int i = 0; i < ransomNote.length(); i++) {
        // 对于金信中的每一个字符都在数组中查找
        // 找到相应位减一，否则找不到返回false
        if (record[ransomNote.charAt(i) - 'a'] > 0) {
            record[ransomNote.charAt(i) - 'a']--;
        }else {
            return false;
        }
    }
    return true;
}

找到字符串中所有字母异位词：

题目描述：

找到字符串中所有字母异位词（力扣链接🔗）

题目分析：

此题需要在p的固定长度下对s进行遍历判断，此时在遍历s进行范围判断，可以使用滑动窗口的方法，但此时滑动窗口的长度是固定的，在判断固定长度的字符串是否相等，可以映射在一个数组中判断即可（使用数组表示hashtable）。

代码：

   /**
   * 使用固定的滑动窗口和hash表即可
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        int[] record = new int[26]; // hash表记录重复的字符
        // 将p放入hash表中进行判断
        for (int i = 0; i < p.length(); i++) {
            record[p.charAt(i) - 'a']++;
        }
        int right = 0;
        int left = 0;
        List<Integer> list = new ArrayList<>();
        // 滑动窗口中的字符映射的数组
        int[] windows = new int[26];
        while (right < s.length()) {
            // 将字符放入数组
            windows[s.charAt(right) - 'a']++;
            // 在固定的滑动窗口进行判断
            if (right - left + 1 == p.length()) {
                // 如果窗口中的hash数组和p的hash数组相等，即将窗口左侧加入即可
                if (Arrays.equals(windows, record)) {
                    list.add(left);
                }
                // 窗口不匹配时
                // 因为是固定长度，将left中的字符删除，将left向右移动即可
                windows[s.charAt(left) - 'a']--;
                left++;
            }
            right++;
        }
        return list;
    }
}