解法一: 暴力求解. 固定一个数, 向前/向后查找另个一数, 判断是否两数之和为 target
解法二: 哈希优化. 从前向后遍历数组, 每遍历一个元素 nums[i] , 从哈希表中找有没有 target - nums[i] 这个元素, 如果有则返回结果. 如果没有, 再把当前数和其下标绑定放入哈希表中.

注意, 是在遍历的过程中将当前元素和下标放入哈希中, 而不是 "一口气" 全部放入哈希表中, 否则可能重复使用一个元素.

1.2 算法代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // <nums[i], i>
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int val = target - nums[i];
            if(hash.containsKey(val)) {
                return new int[]{i, hash.get(val)};
            }else {
                hash.put(nums[i], i);
            }
        }
        // 照顾编译器
        return new int[]{0, 0};
    }
}

2、面试题 01.02. 判定是否互为字符重排

. - 力扣（LeetCode）

2.1 算法原理

解法: 哈希表
使用数组自己模拟哈希表 hash[26]:

两个数组 hash1 + hash2 => 记录两个字符串中字符出现的个数, 如果相同字符出现的个数不相等 => false
优化: 一个数组 => 记录第一个字符串中字符出现的个数, 遍历第二个字符串时, 每出现一个字符, 对该字符哈希表中的值进行 -1 操作. 若最终 hash 中每个元素的值都为 0 => true, 反之 => false

2.2 算法代码

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s1.length()) return false;
        int[] hash = new int[26];
        for(int i = 0; i < s1.length(); i++) {
            hash[s1.charAt(i) - 'a']++;
        }
        for(int i = 0; i < s2.length(); i++) {
            hash[s2.charAt(i) - 'a']--;
        }
        for(int x : hash) {
            if(x != 0) return false;
        }
        return true;
    }
}

3、217. 存在重复元素

. - 力扣（LeetCode）

3.1 算法原理

使用哈希,

每遍历一个元素, 从哈希表中看看有没有相同的元素, 有的话直接返回 true. 没有的话把当前元素放到哈希中, 继续向后遍历.
遍历完若还没有返回, 说明整个数组中没有重复的元素 => false

3.2 算法代码

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

4、219. 存在重复元素 II

. - 力扣（LeetCode）

4.1 算法原理

核心: 哈希表

从前往后遍历, 将数组元素和下标绑定, 放到哈希表中
每遍历一个元素, 从哈希中找有没有重复的元素, 并且下标之差小于 k
若发现有元素满足上述两个条件, 返回 true
当全部遍历完后, 没有进行返回, 则说明整个数组中没有重复的元素, 返回 false

注意: 由于 Map 天然去重的特性, 当相同的元素(Key)重复放入, 可能会发生覆盖现象.

但是本题不影响, 因为新放入的数据是最近的下标, 当后续有元素重复时, get 得到位置是最近位置.

4.2 算法代码

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(hash.containsKey(nums[i]) && Math.abs(hash.get(nums[i]) - i) <= k) {
                return true;
            }else {
                hash.put(nums[i], i);
            }
        }
        return false;
    }
}

5、49. 字母异位词分组

. - 力扣（LeetCode）

5.1 算法原理

哈希表 => <String, List<String>>

将字符串进行排序:
如果排完序的字符串在哈希表中存在, 则说明存在字母异位词, 把原本的字符串放进 List<String> 中

5.2 算法代码

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            List<String> list = map.getOrDefault(String.valueOf(ch), new ArrayList<>());
            list.add(str);
            map.put(String.valueOf(ch), list);
        }
        return new ArrayList<>(map.values());
    }
}

END