Hot100

热题100 哈希 1. 两数之和 给定： 数组nums 和target 要求：找出两元素之和为target的数组下标 暴力： 1for i in range(len(nums)): 2 for j in range(i+1, len(nums)): 3 if ... 4# O(n^2) 题解： 问题分解 => 给定x 寻找 target-x(这是复杂度的主要部分) 用额外结构记录 1hashtable = dict() 2for i in range(len(nums)): 3 if nums[i] in hashtable: 4 return [i, hashtable[nums[i]]] 5 else: 6 hashtable[nums[i]] = i 7# 保存遍历过的元素，参考过去 ⭐思路：target = num1 + num2 => 已知num1 求num2 => 寻找 target - num1 寻找过程：hash存储，这样可以 O(1) 查找 另一个 49. 字母异位词分组 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]] 思路：condition => […] HashTable, Key=排序后的Str, Value=List<String> 1HashMap<String, List<String>> hashTable = new HashMap<>(); 2for(String str : strs){ 3 char[] charArray = str.toCharArray(); // 将字符串转换为字符数组 4 Arrays.sort(charArray); // 对字符数组进行排序 5 String orderStr = new String(charArray); 6 if (hashTable.containsKey(orderStr)) { 7 hashTable.get(orderStr).add(str); 8 }else { 9 hashTable.put(orderStr, new ArrayList<>()); 10 hashTable.get(orderStr).add(str); 11 } 12} 13 14List<List<String>> res = new ArrayList<>(); 15 16for (Map.Entry<String, List<String>> entry : hashTable.entrySet()) { 17 res.add(entry.getValue()); 18} 19return res; ⭐思路：组合在一起 => eat和tea的共同点 => 均含有aet(顺序的) ...