代码随想录
哈希表
两数之和
思路
暴力枚举
for循环哈希表法
知识点
在Java的HashMap（哈希表的一个实现）中，常用的方法包括：
put(K key, V value)：将指定的键值存入哈希表。如果键已存在，则更新其值。get(Object key)：根据键获取对应的值。如果键不存在，则返回null。remove(Object key)：根据键删除对应键值对。containsKey(Object key)：检查哈希表中是否存在指定的键。containsValue(Object value)：检查哈希表中是否存在指定的值。keySet()：返回哈希表中所有键的集合。value()：返回哈希表中所有值的集合。EntrySet()：返回哈希表中所有键值对的集合。size()：返回哈希表中键值对的数量。isEmpty()：检查哈希表是否为空。
Code
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; ++i){
if (hashtable.containsKey(target - nums[i])){
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}无重复字符的最长子串
思路
滑动窗口
知识点
基于哈希表实现的 Java 类主要包括：
HashMap：用于存储键值对，键唯一。LinkedHashMap：保留插入顺序的哈希表实现，继承自HashMap。TreeMap：基于红黑树实现，按键的自然顺序或指定的比较器排序。HashSet：存储不重复的元素，底层使用HashMap。LinkedHashSet：保留插入顺序的集合，底层使用LinkedHashMap。EnumMap：专门为枚举类型设计的哈希表实现，效率高。
Java 中 String 类的常用方法包括：
length()：返回字符串的长度。charAt(int index)：返回指定索引位置的字符。substring(int beginIndex, int endIndex)：返回从指定索引开始到结束索引的子字符串。indexOf(String str)：返回指定子字符串首次出现的位置，如果未找到返回 -1。lastIndexOf(String str)：返回指定子字符串最后一次出现的位置。contains(CharSequence sequence)：检查字符串是否包含指定的字符序列。equals(Object obj)：比较字符串内容是否相等。equalsIgnoreCase(String anotherString)：忽略大小写比较字符串。toLowerCase()：将字符串转换为小写。toUpperCase()：将字符串转换为大写。trim()：去掉字符串两端的空格。split(String regex)：根据指定的正则表达式分割字符串，返回字符串数组。
Code
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}数组|字符串
多数元素
思路
我们知道出现次数最多的元素大于 ⌊n/2⌋ 次，所以可以用哈希表来快速统计每个元素出现的次数。
我们使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。
我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。
知识点
Map接口的定义
public interface Map<K, V> { //K和V是类型参数，分别表示键(Key)和值(Value)的类型
V put(K key, V value); //保存键值对，如果原来有key，覆盖，返回原来的值
V get(Object key); //根据键获取值， 没找到，返回null
V remove(Object key); //根据键删除键值对， 返回key原来的值，如果不存在，返回null
int size(); //查看Map中键值对的个数
boolean isEmpty(); //是否为空
boolean containsKey(Object key); //查看是否包含某个键
boolean containsValue(Object value); //查看是否包含某个值
void putAll(Map<? extends K, ? extends V> m); //保存m中的所有键值对到当前Map
void clear(); //清空Map中所有键值对
Set<K> keySet(); //获取Map中键的集合
Collection<V> values(); //获取Map中所有值的集合
Set<Map.Entry<K, V>> entrySet(); //获取Map中的所有键值对
interface Entry<K, V> { //嵌套接口，表示一条键值对
K getKey(); //键值对的键
V getValue(); //键值对的值
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
boolean equals(Object o);
int hashCode();
}
boolean containsValue(Object value);
Set<K> keySet();《Java编程的逻辑》第十章
Code
class Solution {
private Map<Integer, Integer> countNums(int[] nums) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!counts.containsKey(num)) {
counts.put(num, 1);
} else {
counts.put(num, counts.get(num) + 1);
}
}
return counts;
}
public int majorityElement(int[] nums) {
Map<Integer, Integer> counts = countNums(nums);
Map.Entry<Integer, Integer> majorityEntry = null;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
majorityEntry = entry;
}
}
return majorityEntry.getKey();
}
}
