哈希表

哈希表基础

哈希表的特点？

答案：

• 键值对存储
• 查找、插入、删除平均O(1)
• 空间换时间
• 可能有哈希冲突

Java中的哈希表

// HashMap
Map<String, Integer> map = new HashMap<>();
map.put("key", 1);
int value = map.get("key");
boolean exists = map.containsKey("key");

// HashSet
Set<Integer> set = new HashSet<>();
set.add(1);
boolean contains = set.contains(1);

哈希表应用

两数之和（LeetCode 1）

答案：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[0];
}

字母异位词分组（LeetCode 49）

答案：

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();

    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        map.putIfAbsent(key, new ArrayList<>());
        map.get(key).add(str);
    }

    return new ArrayList<>(map.values());
}

最长连续序列（LeetCode 128）

答案：

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }

    int maxLength = 0;
    for (int num : set) {
        // 只从序列起点开始计数
        if (!set.contains(num - 1)) {
            int currentNum = num;
            int currentLength = 1;

            while (set.contains(currentNum + 1)) {
                currentNum++;
                currentLength++;
            }

            maxLength = Math.max(maxLength, currentLength);
        }
    }
    return maxLength;
}

无重复字符的最长子串（LeetCode 3）

答案：

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int maxLength = 0;
    int left = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        if (map.containsKey(c)) {
            left = Math.max(left, map.get(c) + 1);
        }

        map.put(c, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

哈希表+前缀和

和为K的子数组（LeetCode 560）

答案：

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);

    int count = 0;
    int sum = 0;

    for (int num : nums) {
        sum += num;
        if (map.containsKey(sum - k)) {
            count += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}

连续数组（LeetCode 525）

答案：

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);

    int maxLength = 0;
    int sum = 0;

    for (int i = 0; i < nums.length; i++) {
        sum += nums[i] == 1 ? 1 : -1;

        if (map.containsKey(sum)) {
            maxLength = Math.max(maxLength, i - map.get(sum));
        } else {
            map.put(sum, i);
        }
    }
    return maxLength;
}

LRU缓存

LRU缓存（LeetCode 146）

答案：

class LRUCache {
    private Map<Integer, Node> map;
    private int capacity;
    private Node head, tail;

    class Node {
        int key, value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        remove(node);
        addToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            remove(node);
            addToHead(node);
        } else {
            if (map.size() == capacity) {
                map.remove(tail.prev.key);
                remove(tail.prev);
            }
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
        }
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
}

练习题

1. 有效的字母异位词（LeetCode 242）
2. 两个数组的交集（LeetCode 349）
3. 快乐数（LeetCode 202）
4. 同构字符串（LeetCode 205）
5. 前K个高频元素（LeetCode 347）