LeetCode 热题 HOT 100：哈希表专题

谁借莪１个温暖的怀抱￠ 2023-10-15 15:17 12阅读 0赞

LeetCode 热题 HOT 100：[https://leetcode.cn/problem-list/2cktkvj/][https_leetcode.cn_problem-list_2cktkvj]

--------------------

#### 文章目录 ####

*   *  1. 两数之和
     *  49. 字母异位词分组
     *  136. 只出现一次的数字
     *  141. 环形链表
     *  142. 环形链表 II

--------------------

### 1. 两数之和 ###

题目链接：[https://leetcode.cn/problems/two-sum/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][https_leetcode.cn_problems_two-sum_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]

暴力做法：

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            for(int i = 0; i < nums.length; i ++){
        
                for(int j = i+1; j < nums.length; j ++){
        
                    if(nums[i] + nums[j] == target){
        
                        return new int[]{
        i, j};
                    }
                }
            }
            return new int[0];
        }
    }

哈希表：

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            Map<Integer, Integer> map = new HashMap<>();// key：数组元素的值，value：数组索引
            for(int i = 0; i < nums.length; i ++){
        
                if(map.containsKey(target - nums[i])){
        
                    return new int[]{
        map.get(target-nums[i]), i};
                }
                map.put(nums[i], i);
            }
            return new int[0];
        }
    }

注意：不要先存 map，在去遍历比较。  
如：nums=\[3,2,4\]，map 中存储了 3–>0、2–>1、4–>2，但是当比较 map 中是否含有 3 时，直接就返回 \[0,0\]。

--------------------

### 49. 字母异位词分组 ###

题目链接：[https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked][https_leetcode.cn_problems_group-anagrams_description_envType_study-plan-v2_envId_top-100-liked]

class Solution {
        
        public List<List<String>> groupAnagrams(String[] strs) {
        
            List<List<String>> res = new ArrayList<>();
            HashMap<String, List<String>> map = new HashMap<>(); // key：排序后的字符串，value 字母异位词分组
            for (int i = 0; i < strs.length; i++) {
        
                char[] chs = strs[i].toCharArray();
                Arrays.sort(chs); // 将字符串数组排序，排序后的值作为 map 的 key 
                String key = new String(chs);
                if(map.containsKey(key)){
        
                    map.get(key).add(strs[i]);
                }else{
        
                    map.put(key, new ArrayList<>(Arrays.asList(strs[i])));
                }
            }
            for (Map.Entry<String, List<String>> entry: map.entrySet()){
        
                res.add(entry.getValue());            
            }
            return res;
        }
    }

另一种实现思路，手动构造key的形式：

class Solution {
        
        public List<List<String>> groupAnagrams(String[] strs) {
        
            List<List<String>> res = new ArrayList<>();
            Map<String, List<String>> map = new HashMap<>();
            for (int i = 0; i < strs.length; i++) {
        
                char[] chs = strs[i].toCharArray();
                int[] letter = new int[26];
                for (int j = 0; j < chs.length; j++) {
        
                    letter[chs[j] - 'a'] ++;
                }
                // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < letter.length; j ++){
        
                    if(letter[j] != 0){
        
                        sb.append((char)(j+'a'));
                        sb.append(letter[j]); 
                        // 因为会出现 "aab"，"abb"的情况，如果不加会当成同一个key
                        // 加上后构造的key：aab --> a2b1、abb ---> a1b2
                    }
                }
                String key = sb.toString();
                List<String> list = map.getOrDefault(key, new ArrayList<>());
                list.add(strs[i]);
                map.put(key, list);
            }
    
            for(Map.Entry<String, List<String>> entry: map.entrySet()){
        
                res.add(entry.getValue());
            }
            return res;
        }
    }

--------------------

### 136. 只出现一次的数字 ###

题目链接：[https://leetcode.cn/problems/single-number/?envType=study-plan-v2&envId=top-100-liked][https_leetcode.cn_problems_single-number_envType_study-plan-v2_envId_top-100-liked]

哈希表做法（算法复杂度较高）：

class Solution {
        
        public int singleNumber(int[] nums) {
        
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
        
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
        
                if(entry.getValue() == 1){
        
                    return entry.getKey();
                }
            }
            return 0;
        }
    }

异或做法：

*  一个数和 0 做异或运算等于本身，如：**`a⊕0 = a`**
 *  一个数和其本身做异或运算等于 0，如：**`a⊕a = 0`**
 *  XOR 运算满足交换律和结合律：**`a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b`**
 *  题目本身限制 nums 数组中，除了仅有一个值出现一次，其余元素全部出现两次  
    因此，重复元素 ⊕ 唯一值 ⊕ 重复元素 = 唯一值，
 *  以此类推：重复元素1⊕唯一值⊕重复元素1⊕重复元素2⊕重复元素2 = 唯一值

class Solution {
        
        public int singleNumber(int[] nums) {
        
            int ans = 0; // 初值为0，是因为 0⊕任何值 = 任何值
            for(int i = 0; i < nums.length; i ++){
        
                ans ^= nums[i];
            }
            return ans;
        }
    }

--------------------

### 141. 环形链表 ###

题目链接：[https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked][https_leetcode.cn_problems_linked-list-cycle_description_envType_study-plan-v2_envId_top-100-liked]

哈希表做法（时间复杂度较高）：

public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            if(head == null){
        
                return false;
            }
            Set<ListNode> set = new HashSet(); // set 记录结点的地址
            while(head.next != null){
        
                if(set.contains(head)){
        
                    return true;
                }
                set.add(head);
                head = head.next;
            }
            return false;
        }
    }

快慢指针做法1：

public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            if(head == null){
        
                return false;
            }
            ListNode slow, fast;
            slow = head;
            fast = head.next;
            // slow 每次向前走一步，fast 每次向前走两步（可以任意多步）
            // 当存在环时，fast 由于走得快，会发生扣圈的情况，且最终与 slow 相遇
            // 当不存在环时，fast 可能在某次循环后，发生当前位置为空，或下一位置为空的两种情况，当然由于走的快，最终会返回false。
            // 总之，循环的结束条件，要么出现环 slow == fast，要么 fast 先一步为空！ 
            while(slow != fast && fast != null && fast.next != null){
        
                // 注意：fast != null 要先于fast.next != null 来判断，以防止控制帧异常
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow == fast;
        }
    }

快慢指针做法2（思路同下方“环形链表2”）：

public class Solution {
        
        public boolean hasCycle(ListNode head) {
        
            ListNode slow = head, fast = head;
    
            while(true){
        
                if(fast==null || fast.next==null){
        
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
                if(slow==fast){
        
                    return true;
                }
            }
        }
    }

--------------------

### 142. 环形链表 II ###

题目链接：[https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked][https_leetcode.cn_problems_linked-list-cycle-ii_envType_study-plan-v2_envId_top-100-liked]

哈希表做法（时间复杂度较高）：

public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            Set<ListNode> set = new HashSet<>();
            ListNode p = head;
            while(p!=null){
        
                if(set.contains(p)){
        
                    return p;
                }
                set.add(p);
                p = p.next;
            }
            return null;
        }
    }

快慢指针，实现思路如下：

*  设 **`fast`** 每次走两个节点， **`slow`** 每次走一个节点。环外有 **`a`** 个结点，环内有 **`b`** 个结点。
 *  相遇时，**`fast`** 走了 **`f`** 步，**`slow`** 走了 **`s`** 步。  
    ① **`f = 2s`**  
    ② **`f = s + nb`** 表示 **`f`** 比 **`s`** 多走了 **`n*b`** 步，即 **`n`** 圈。这样表示的原因在于扣圈。  
    化简得：**`f = 2nb, s = nb`**
 *  设刚开始 **`slow`** 指针从开始到环的入口要走 k 步：**`k = a + nb （n = 0,1,2,…）`**
 *  由于 **`s = n*b`**，即已经走了 **`n*b`** 步了，那么此时只需要再走 **`a`** 步即可回到链表入环的起点。

public class Solution {
        
        public ListNode detectCycle(ListNode head) {
        
            ListNode fast = head, slow = head;
            while(true){
        
                if(fast == null || fast.next == null){
        
                    return null;
                }
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow){
        
                    break;
                }
            }
            fast = head; // fast回到链表起点，与 slow 一同遍历 a 步
            while(slow != fast){
        
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
    }

[https_leetcode.cn_problem-list_2cktkvj]: https://leetcode.cn/problem-list/2cktkvj/
[https_leetcode.cn_problems_two-sum_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/two-sum/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_group-anagrams_description_envType_study-plan-v2_envId_top-100-liked]: https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
[https_leetcode.cn_problems_single-number_envType_study-plan-v2_envId_top-100-liked]: https://leetcode.cn/problems/single-number/?envType=study-plan-v2&envId=top-100-liked
[https_leetcode.cn_problems_linked-list-cycle_description_envType_study-plan-v2_envId_top-100-liked]: https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked
[https_leetcode.cn_problems_linked-list-cycle-ii_envType_study-plan-v2_envId_top-100-liked]: https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked