- 哈希表基础
- 哈希表写题基础
- 字符串类
- 有效的字母异位词
- ArrayList用法
- 两个数组的交集
- 两数之和
哈希表基础
哈希函数： 哈希表使用哈希函数将键转换为数组的索引。理想情况下，哈希函数应该将键均匀分布在数组中，以减少冲突（两个键映射到同一个索引）的可能性。
数组： 哈希表底层通常是一个数组，数组的每个槽位可以存储一个或多个键值对。
冲突解决： 当两个或更多的键哈希到同一个索引时，会发生冲突。Java的HashMap通过链表或红黑树来解决冲突：
链地址法（Separate Chaining）：在发生冲突时，元素将被添加到该索引处的链表中。从Java 8开始，当链表长度超过一定阈值（默认为8）时，链表会转换为红黑树，以提高效率。
开放地址法（Open Addressing）：不是Java HashMap的实现方式，但在其他语言或库中可能会看到。这种方法通过寻找数组中的另一个空槽来解决冲突。
哈希表写题基础
什么时候用哈希表？
一般哈希表都是用来快速判断一个元素是否出现集合里。例如要查询一个名字是否在这所学校里。要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。
怎么用哈希表
1.数组模拟
针对给的数据范围比较小，这种方式一般性能比较高，代价比较低。
2.java中的HashMap。
针对一般情况，代价比较高。
java中HashMap要掌握的点。
主要了解它的操作。
创建：
HashMap<Integer, String> map = new HashMap<>();
//HashMap的键（Key）和值（Value）必须是对象类型，
//不能直接使用基本数据类型，如 int、double、char 等。
//这是因为Java的集合框架（Collections Framework）是在对象类型上构建的，
//不支持基本类型。
这里补充一个自动装箱，拆箱机制，实现类型转对象
Java提供了自动装箱（autoboxing）和拆箱（unboxing）机制，这使得在使用基本数据类型和它们的包装类（如 Integer、Double、Character 等）时更加方便。
装箱（Autoboxing）：自动将基本数据类型转换为相应的对象类型。例如，当你将一个 int 类型的值放入 HashMap 中时，它会自动转换为 Integer 对象。
拆箱（Unboxing）：自动将对象类型转换回基本数据类型。例如，从 HashMap 中取出一个 Integer 对象时，可以自动转换为 int 类型。
看一个例子
HashMap<Integer, Integer> map = new HashMap<>();
int key = 1;
int value = 100;
// 自动装箱：int 转为 Integer
//也就是说定义归定义，但是用的时候可以直接用，尽管你是普通类型，但是会自动装修
map.put(key, value);
// 自动拆箱：从 HashMap 获取的 Integer 自动转为 int
//获取里面的东西，可以直接赋给普通类型的，会自动拆箱。
int retrievedValue = map.get(key);
System.out.println("Value: " + retrievedValue); // 输出: Value: 100
总的来说，声明的时候，用对象类型，但是使用的时候不用考虑对象类型，会自动装拆箱。
插入元素：
map.put(1, "one"); // 将键为1，值为"one"的键值对插入到HashMap中
访问元素：
String value = map.get(1); // 返回键为1的元素的值，如果不存在，则返回null
检查键存在：
boolean hasKey = map.containsKey(1); // 检查键为1的元素是否存在
删除元素：
map.remove(1); // 删除键为1的元素
遍历：
for (Map.Entry<Integer, String> entry : map.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
特性：
无序：HashMap不保证元素的顺序，元素的存储取决于哈希函数。
键的唯一性：每个键在HashMap中必须是唯一的。
null键和null值：HashMap允许使用一个null键和多个null值。
时间复杂度：理想情况下，HashMap的get和put操作的时间复杂度为O(1)。但在最坏的情况下（大量冲突时），复杂度可能退化到O(n)。
字符串类
在做下面的题需要用到很多字符串的知识，这里进行补充。
String 类是一个非常重要且常用的类，用于表示和操作字符序列。由于 String 在Java中是不可变的（immutable），任何修改 String 的操作都会生成一个新的 String 对象，而不是修改原始对象。这种设计有助于提高程序的安全性和效率，尤其是在多线程环境中。
创建字符串
直接赋值：String s = “Hello”;
通过构造函数：String s = new String(“Hello”);
相关常用api：
长度：
int length()：返回字符串的长度。 ★
字符访问：
char charAt(int index)：返回指定索引处的字符。 ★
int indexOf(int ch)：返回指定字符首次出现的字符串内的索引。
int indexOf(String str)：返回指定子字符串首次出现的字符串内的索引。
int lastIndexOf(int ch)：返回指定字符最后一次出现的索引。
int lastIndexOf(String str)：返回指定子字符串最后一次出现的索引。
字符串比较：
boolean equals(Object anotherObject)：比较两个字符串的内容是否相同。
boolean equalsIgnoreCase(String anotherString)：忽略大小写比较两个字符串。
int compareTo(String anotherString)：字典顺序比较两个字符串。
子字符串：
String substring(int beginIndex)：返回一个新的字符串，它是此字符串的一个子字符串，从指定索引开始到结尾。
String substring(int beginIndex, int endIndex)：返回一个新字符串，它是此字符串的一个子字符串，从 beginIndex 开始到 endIndex-1。
字符串修改：
String concat(String str)：将指定字符串连接到此字符串的结尾。
String replace(char oldChar, char newChar)：返回一个新字符串，它是通过用 newChar 替换此字符串中出现的所有 oldChar 得到的。
String trim()：返回此字符串移除了前导和尾部空白的副本。 ★
String toLowerCase()：使用默认语言环境的规则将此 String 中的所有字符都转换为小写。
String toUpperCase()：使用默认语言环境的规则将此 String 中的所有字符都转换为大写。
搜索和替换：
boolean startsWith(String prefix)：测试此字符串是否以指定的前缀开始。
boolean endsWith(String suffix)：测试此字符串是否以指定的后缀结束。
String[] split(String regex)：根据匹配给定的正则表达式来拆分此字符串
转换：
char[] toCharArray()：将此字符串转换为一个新的字符数组。 ★
掌握几个打星的即可。
有效的字母异位词
想到统计字符串每个字符的个数，那想到的就是遍历字符串进行累加。这很容易想到用哈希的思想。所以这里的做法主要就是哈希。
哈希有数组模拟，也可以用HashMap映射。
这里由于数据范围有限，所以用数组模拟就比较好。所以这里有
解法1：
开一个长度为26的int类型的数组。利用字符之间运算可以得到int数字来确认下标。这样也可以完成对应字符数的统计。
扫描字符串1，利用charAt()获取字符，然后进行统计++。
再去扫描字符串2，但是对应字符的进行相减抵消
最后检查数组是否全0，全0代表全部字符抵消，那就是两个字符串每个字符的数量相同。
class Solution {
public boolean isAnagram(String s, String t) {
int[] num = new int[26]; //创建数组，对应26个英文字母
for(int i = 0;i<s.length();i++){
num[s.charAt(i)-'a']++; //扫描字符串s，进行字符统计
}
for(int i = 0;i<t.length();i++){
num[t.charAt(i)-'a']--; //扫描字符串t,进行字符抵消
}
for(int i = 0;i<num.length;i++){
if(num[i] !=0){
return false; //扫描统计数组，看是否全为0，完成抵消
}
}
return true;
}
}
ArrayList补充 注意是个类
ArrayList 是一种基于数组实现的可变大小的动态数组类，它属于 java.util 包。与普通数组相比，ArrayList 可以动态地增加和减少元素，这使得它在处理不确定数量的数据时非常有用，特别是在算法和数据结构问题中。
主要特点
动态扩容：ArrayList 的容量可以根据需要自动增加，当添加元素使得内部数组容量不足时，ArrayList 会自动创建一个新的更大的数组，并将旧数组的内容复制到新数组中。
随机访问：ArrayList 支持快速随机访问，即可以在常数时间内访问任何位置的元素，这是因为它内部是通过数组实现的。
类型安全：ArrayList 是泛型类，可以指定存储在其中的元素类型，这样可以在编译时期就检查到类型错误。
使用：
1.导包：
import java.util.ArrayList;
2.创建 ArrayList
不带初始容量的创建：
ArrayList<Integer> list = new ArrayList<>();
带初始容量的创建：
ArrayList<Integer> list = new ArrayList<>(10); // 初始容量为10
常用方法
添加元素：
add(E e)：在列表的末尾添加一个元素。
add(int index, E element)：在指定位置添加一个元素，其他元素向后移动。
访问元素：
get(int index)：返回指定位置的元素。
修改元素：
set(int index, E element)：替换指定位置的元素，并返回原来的元素。
删除元素：
remove(int index)：删除指定位置的元素，返回被删除的元素。
remove(Object o)：删除指定的对象，如果存在的话。
大小和清空：
size()：返回列表中的元素个数。
clear()：删除列表中的所有元素。
判断和搜索：
isEmpty()：判断列表是否为空。
contains(Object o)：判断列表是否包含指定的对象。
下面例子包含了增删查改
import java.util.ArrayList;
import java.util.Arrays;
public class ArrayListExample {
public static void main(String[] args) {
// 创建 ArrayList
ArrayList<String> fruits = new ArrayList<>();
// 添加元素
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
// 使用 Arrays.asList 初始化另一个 ArrayList
ArrayList<String> vegetables = new ArrayList<>(Arrays.asList("Carrot", "Potato", "Cabbage"));
// 访问元素 get() 也是利用下标
System.out.println("First fruit: " + fruits.get(0)); // 输出 Apple
// 修改元素 set() 也是利用下标
fruits.set(1, "Blueberry"); // 将 Banana 替换为 Blueberry
// 遍历 ArrayList可以用增强for
System.out.println("Fruits:");
for (String fruit : fruits) {
System.out.println(fruit);
}
// 删除元素 可以按值删，也可以按下标删
fruits.remove("Cherry"); // 删除元素 Cherry
fruits.remove(0); // 删除索引为 0 的元素（现在是 Apple）
// 判断是否为空 判空函数isEmpty()
if (!fruits.isEmpty()) {
System.out.println("Fruits list is not empty.");
}
}
}
注意ArrayList并不是就是数组，如果结果让你返回数组，那么就是老实遍历ArrayList构建结果数组。还是for遍历，ArrayList的长度是size(),
两个数组的交集
思路：哈希
题目还是限定了数字的范围，所以还是可以用数组模拟哈希的做法。但是这次使用boolean数组不用int，主要是方便设置元素已经加入结果集。
流程：
1.先遍历nums1，统计出现的字符到num1。
2.然后再去遍历nums2，去num1中查找是否出现过，出现过就加入结果集，然后把对应的num1的值置为false，防止后续再次加入。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
boolean[] num1 = new boolean[1005]; //哈希表，用于统计出现数字。
ArrayList<Integer> result = new ArrayList<>(); //存结果集
for(int i = 0;i<nums1.length;i++){
num1[nums1[i]] = true;
}
for(int i = 0;i<nums2.length;i++){
if(num1[nums2[i]] != false){
result.add(nums2[i]);
num1[nums2[i]] = false;
}
}
int[] resultArray = new int[result.size()];
for(int i = 0;i<resultArray.length;i++){
resultArray[i] = result.get(i);
}
return resultArray;
}
}
方法2：排序，然后双指针。
两数之和
两个for就慢了，一个for就用哈希。因为哈希的作用就是优化查找到O（1）
这个哈希有值得学习的技巧。
如果起手按之前的思路无脑先遍历收集。那么就会出现新的问题：
比如[3,3]这种，如果用遍历思想，那就还要多加一个判断是不是同一个元素，十分的麻烦。
正确思路：
首先这种思路突破了一件事，为什么会有上面说的多加一个判断这种问题，那是因为按这种思路，最终每个元素都会访问两次。这里的优化就是直接走到底。不回头。
所以我总结为：哈希走到底，不回头。边走边处理
还有有时候结果只要求存两个结果，那就可以这样开两个数组返回。很方便。
流程：
1.创建一个哈希表，key是数组里的数字，value是该数字在数组中的下标。
2.创建一个长度为2的数组存结果。
3.开始遍历数组，遍历的时候进行其相加的另一个值的计算，然后立即用hash进行查找，（而且题目并不限制答案中谁先谁后）。如果目标元素并不在hash表中，那就把这个数字加入hash表。这样可以发现一直在往前走，并没有元素的重复访问。所以当一旦发现目标元素时，是不用担心元素是同一个元素的风险。因为他是进行判断后才加入到hash中。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> hmap = new HashMap<>();//创建一个hash表
int[] result = new int[2]; //结果集
for(int i = 0;i<nums.length;i++){//遍历数组
int temp = target - nums[i]; //计算另一个目标结果
if(hmap.containsKey(temp)){ //查看目标结果是否在扫过的hash表中。
result[1] = i; //如果在就把当前的下标加入结果集
result[0] = hmap.get(temp); //将另一个目标元素，通过hash获取其下标也加入结果集
return result; //直接返回结果
}
hmap.put(nums[i],i); //如果没有找到，那就把该元素加入hash中。
}
return null;
}
}
//这样始终在处理前面，就不会导致遍历做法中，两次访问到同一元素的问题。