时间问题，哈希表理论基础暂且按下不表，直接进入题目笔记。

242.有效的字母异位词

• 题目描述
  给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
  示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true
  示例 2: 输入: s = “rat”, t = “car” 输出: false
  说明: 你可以假设字符串只包含小写字母。

牢记题目要求判断某元素是否在集合中出现时适合使用哈希表。由于题目给出“字符串只包含小写字母”的条件，因此本题可以直接使用一个长度为26的数组存储一个字符串中的字符种类和出现次数。以下标表示26个小写字母，对应的元素表示该字母出现的次数。
当两个字符串长度不相等时，两者不可能是字母异位词。在两个字符串长度相等的前提下，遍历第一个字符串时，记录第一个字符串的字母种类和出现次数。遍历第二个字符串时，依次在存储的数组中对应位置的元素上扣减次数。如果扣减次数后元素小于0，就意味着这个对应位置字母并没有在第一个字符串中出现/在第二个字符串中多出现了，即可返回false。反之若遍历完第二个字符串后存储数组的所有元素均等于0，意味着两个字符串的字母种类和出现次数相等，满足字母异位词的条件，则返回true。
代码如下：

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] count = new int[26];

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            count[c - 'a']++;  // 该小写字母与'a'的距离之差即为其在数组中存储的位置
        }
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            count[c - 'a']--;
            if (count[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

附记：进阶版题目将字符串中字符的范围放宽至所有Unicode字符，此时再使用数组就不现实了。因为需要同时记录字符种类和出现次数，所以对于进阶版题目，使用HashMap存储键值对更合适。思路上并没有太大的区别，遍历第一个字符串时，将字符作为Key，出现次数作为Value存储至HashMap中，遍历第二个字符串时，以字符作为Key查找对应的值并在此基础上扣减，如果扣减后Value < 0则证明两字符串不为字母异位词。反之，若遍历完第二个字符串后HashMap中存储的所有键值对的值均为0，则两字符串互为字母异位词。

import java.util.HashMap;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        HashMap<Character, Integer> count = new HashMap<Character, Integer>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            count.put(c, count.getOrDefault(c, 0) + 1);  // 若直接使用.get()，当HashMap中不存在该键时会报空指针异常，因此使用.getOrDefault()，当不存在该键时返回给定的默认值
        }
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            count.put(c, count.getOrDefault(c, 0) - 1);
            if (count.get(c) < 0) {
                return false;
            }
        }
        return true;
    }
}

349. 两个数组的交集

• 题目描述
  给定两个数组，编写一个函数来计算它们的交集。输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
  • 示例 1：
    输入：nums1 = [1,2,2,1], nums2 = [2,2]
    输出：[2]
  • 示例 2：
    输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出：[9,4]
    解释：[4,9] 也是可通过的

由于本题只需要输出元素，因此适合使用HashSet。遍历第一个数组时，将数组内的元素存储至HashSet内，这个存储过程就会自动去重。之后，遍历第二个数组，当发现这个元素属于交集时，存储至另一个HashSet内避免最终输出的结果重复。最后，将HashSet转换为方法要求的数据结构int数组即可。

import java.util.HashSet;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> count = new HashSet<Integer>();
        HashSet<Integer> compare = new HashSet<Integer>();
        
        for (int i = 0; i < nums1.length; i++) {
            count.add(nums1[i]);
        }
        for (int j = 0; j < nums2.length; j++) {
            if (count.contains(nums2[j])) {
                compare.add(nums2[j]);
            }
        }
        
        int[] result = new int[compare.size()];
        int index = 0;
        for (int c : compare) {
            result[index++] = c;
        }
        
        return result;
    }
}

附记：卡哥博客内给出的Java题解并不是像上面自己写的代码那样将HashSet转换为int数组的，而是使用了return resSet.stream().mapToInt(x -> x).toArray();。通过资料大概了解，stream是Java 8 特性之一，可以将数据转换为流进行处理。.mapToInt(x -> x)的作用是将HashMap内的元素原封不动（匿名函数处）转换为Integer，然后再将这些元素输出至数组。时间问题没有深入学习，但这一行代码拿来做什么的是搞明白了。

202. 快乐数

• 题目描述
  编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。如果 n 是快乐数就返回 True，不是则返回 False 。
  • 示例：
    输入：19
    输出：true
    解释：
    1^2 + 9^2 = 82
    8^2 + 2^2 = 68
    6^2 + 8^2 = 100
    1^2 + 0^2 + 0^2 = 1

初看题目，这个无限循环属实是让人头大，很容易让人反复寻找终止循环条件而不得。但反向思考的话，无限循环同时也意味着运算结果反复出现（否则无法构成循环），这就是这道题终止循环，判断结果的关键所在。既然又是判断元素是否在集合中出现过，那么这道题依然是使用哈希表的。因为事先无法确定循环的长度，又只需存储每一步运算的结果，所以本题适合使用 HashSet。
根据上述分析，终止循环的条件有二，其一是 n 的最终运算结果为1，其二是 n 的运算结果能够在 HashSet 中找到，因前者而终止循环则输出 true，因后者而终止循环则输出 false。

import java.util.HashSet;

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> store = new HashSet<>();
        int res = 0;
        while (n != 1 && !store.contains(n)) {  // 两个终止循环的条件
            store.add(n);
            n = getNextValue(n);
        }
        return n == 1;
    }
    private int getNextValue(int n) {  // 按照题目给定方法计算 n 
        int res = 0;
        while (n > 0) {
            int tmp = n % 10;
            res += tmp * tmp;
            n /= 10;
        }
        return res;
    }
}

1. 两数之和

• 题目描述
  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
  • 示例 1：
    输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

题目给出的提示是每种输入只会对应一个答案，换言之，如果用 target 依次减去数组中的所有元素，其差值构成一个新的数组，只有满足题目要求的两个数字会再次在这个数组中出现。因此，题目可以变形成在这个新的数组中寻找原数组的元素是否存在，符合使用哈希表的条件。
由于没有思路，直接学习了卡哥博客里的Java解法。

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> record = new HashMap<Integer, Integer>();  // 用于存储元素和对应的下标，由于题目要求返回的是下标，因此以元素值为Key，以下标为Value
        int[] result = new int[2];

        for (int i = 0; i < nums.length; i++) {
            if (!record.containsKey(target - nums[i])) {  // 如果没找到能够成对的结果，就将元素自己和它对应的下标存储进HashMap中
                record.put(nums[i], i);
            } else {
                result[0] = record.get(target - nums[i]);  // 找到了成对的结果即可直接输出
                result[1] = i;
                break;
            }
        }
        return result;
    }
}

原文地址：http://www.cnblogs.com/renewable/p/16800856.html