哈希题目总结

以下列举了可以用哈希方法（包括但不限于用HashMap和HashSet）的题目，实质上是把东西丢给这些数据结构去维护。请注意有些题目中用哈希是最优解，有些题目中不是最优解，可以自行探索其时间复杂度和空间复杂度的区别，思考优化的方法（位运算或者原地排序等）。x数之和/差的专题多半都可以用哈希方法。

1 重复元素

1.1、查询/判断是否有重复元素

存在重复元素：给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回true。如果数组中每个元素都不相同，则返回false。

数组中重复的数字：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return true;
            }
            set.add(num);
        }
        return false;
    }
}

1.2、判断是否存在重复元素（距离不超过K）

存在重复元素 II：给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引i和j，使得 nums[i] = nums[j]，并且i和j的差的绝对值至多为k。

思路：哈希map保存 <num, index>

num 重复出现时，更新 index，保证和后面的工作指针更靠近；

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        //保证了 num再次出现时, index肯定是更靠近工作指针的
        for (int i=0; i<nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if (Math.abs(i - map.get(nums[i])) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

1.3、是否存在重复元素（距离&value差满足一定条件）

存在重复元素 III：在整数数组nums中，是否存在两个下标i 和j，使得nums[i]和nums[j] 的差的绝对值小于等于t，且满足i和j的差的绝对值也小于等于ķ。如果存在则返回true，不存在返回false。

思路：桶

定义 Map
- key=桶编号；
- value=具体的num值；
- map中的数据在 abs(i - j)<=indexDiff 范围内，一旦超过就 remove超出的键值对；
对每个元素 num 计算其对应的桶编号；这题的值域范围限制是[-10^9, 10^9]，总数量没有超过有符号整型的正数范围，所以完全可以用更简单的平移法来生成id，避免更多的推导。
检测桶i、i-1、i+1 在map中是否存在，如果存在则自动满足 indexDiff条件，下面判断是否满足valueDiff条件即可
- 桶 i 内已经存在元素 x，那么 abs(x-num) 肯定满足 valueDiff，返回true；
- 桶 i-1、i+1 需要额外判断是否满足 abs(x-num)
其他桶就不需要检测了，abs(x-num) 肯定不满足 valueDiff；
如果没找到，就把 num 和桶编号放入到map中；
最后删除不满足 indexDiff的map数据；

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int n = nums.length;
        // key=桶编号, value=具体的num值, map中的数据在 abs(i - j)<=indexDiff 范围内
        Map<Long, Long> map = new HashMap<>();
        //桶大小
        long bucketSize = (long)valueDiff + 1;

        //只要map有值，那么肯定满足 indexDiff的条件，只需要判断 valueDiff的条件即可
        for (int i=0; i<n; i++) {
            //计算元素对应的桶的编号
            long id = getID(nums[i], bucketSize);
            if (map.containsKey(id)) {
                return true;
            }

            //检查相邻的左边桶, 需要满足 abs(nums[i]-nums[j]) <= valueDiff
            if (map.containsKey(id-1) 
                && Math.abs(nums[i] - map.get(id-1)) < bucketSize) {
                return true;
            }
            //检查相邻的右边桶, 需要满足 abs(nums[i]-nums[j]) <= valueDiff
            if (map.containsKey(id+1)
                && Math.abs(nums[i] - map.get(id+1)) < bucketSize) {
                    return true;
            }

            //注意这里肯定不会发生覆盖，因为一旦覆盖就说明两个元素同属一个桶，直接返回true了
            map.put(id, (long)nums[i]);

            //保证map中的数据在 abs(i - j)<=indexDiff 范围内
            if (i >= indexDiff) {
                map.remove(getID(nums[i-indexDiff], bucketSize));
            }
        }
        return false;
    }

    //计算元素所属的桶编号
    private long getID(long x, long bucketSize) {
        //统一正负数
        return (x + 1000000000) / bucketSize;
    }
}

1.4、数组是否存在重复元素（常数空间复杂度&不可修改数组）

寻找重复数：给定一个包含n+1个整数的数组nums，其数字都在1到n之间（包括1和n），可知至少存在一个重复的整数。假设nums只有一个重复的整数，找出这个重复的数。

注意：题目要求不修改原数组 & 常量空间复杂度；

思路：Floyd 判圈算法

找到相遇点：value=6

class Solution {
    public int findDuplicate(int[] nums) {
        //Floyd 判圈算法
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        //注意此时可能指向的同一个index，而不是不同index的相同value

        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

2 数组交集

两个数组的交集：输出结果中的每个元素一定是唯一的。

两个数组的交集 II：输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。

【提升1】如果给定的数组已经排好序呢？你将如何优化你的算法？

【提升2】如果 nums1 的大小比 nums2 小，哪种方法更优？

【提升3】如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

7.3 数字游戏

珠玑妙算：给定一种颜色组合solution和一个猜测guess，编写一个方法，返回猜中和伪猜中的次数answer，其中answer[0]为猜中的次数，answer[1]为伪猜中的次数。
猜数字游戏：请写出一个根据秘密数字和朋友的猜测数返回提示的函数，返回字符串的格式为xAyB，x和y都是数字，A表示公牛，用B表示奶牛。
有效的数独：判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
分糖果：给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。
扑克牌中的顺子：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为14。