基础知识（hello 算法）
https://www.hello-algo.com/chapter_array_and_linkedlist/array/
数组：数组元素存储在连续的内存空间中，如果知道数组首地址和某个元素的索引，查找数据很简单，时间复杂度低O(1)，在数组中插入和删除需要移动元素，所以时间复杂度有点高O(N)。数组（静态）的长度是不可变的（ArrayList动态数组，长度未知的数组），如果扩容数组则重新建立一个更大的数组，复制旧数组的元素到新数组中。
1
2
|
// 数组初始化
int[] nums = {1,2,3} or int[] nums = new int[3];
|
链表：如果数组很大 内存无法提供这么大的连续空间 则可以使用链表这种数据结构。【value,*】， *指针指向下一个节点的内存地址。链表的尾节点指向null。
1
2
3
4
5
6
|
初始化链表 节点1 -> 节点2
// 初始化节点
n0 = listNode(1)
n1 = listNode(2)
// 构建节点之间的引用
n0.next = n1
|
链表的插入和删除很简单，只需要改变引用即可O（1），但是查询数据的时候，需要从头节点向后遍历直到目标节点O(N)。
数组和链表采用了相反的存储策略（一个连续，一个不需要连续），因此各种性质和操作效率都呈对立特点。
链表的种类：单向链表，双向链表，环形链表
1
2
3
4
5
6
7
|
/* 双向链表节点类 */
class ListNode {
int val; // 节点值
ListNode next; // 指向后继节点的引用
ListNode prev; // 指向前驱节点的引用
ListNode(int x) { val = x; } // 构造函数
}
|
列表：元素的有序集合，可以基于数组和链表实现。数组实现的列表是一个有长度限制的列表，因此可以用动态数组来实现列表。列表本质是数组，查找元素很快O（1），插入和删除元素O(N). 列表可以拼接。关于列表的数据结构怎么设计的可以看源码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// 动态数组初始化
import java.util.ArrayList;
import java.util.List;
List<Integer> dynamicList = new ArrayList<>(); // 空列表
dynamicList.add(1); // 添加元素
dynamicList.add(2);
dynamicList.addAll(java.util.Arrays.asList(3, 4, 5)); // 批量添加
//或者
List<Integer> dynamicList2 = new ArrayList<>(10); // 初始容量 10，可自动扩容
// 列表拼接
dynamicList.add(dynamicList2);
// 列表排序（进行完列表排序后 可以使用二分查找和双指针算法）
Collections.sort(dynamicList2);
|
搜索算法：
-
暴力法：通过遍历数据结构中的每个元素定位目标
-
自适应搜索：利用数据的特性（比如有序性）优化搜索过程
数组
二分查找
二分查找是一种基于分治法策略的高效搜索算法，利用数据的有序性，每轮缩小范围直到找到目标或者找不到目标。即给指针low和high分别设置搜索目标，目标可能是一个值，也可能是一个范围，最终他们要么找到目标终止循环，要么越过边界终止循环
二分查找的优点：时间效率高O（logN），不需要额外的空间【哈希算法以空间换时间】
二分查找的局限性：仅适合有序数组（不要想着先对无序数组排序再用二分查找，因为排序的时间复杂度就已经很高了），不能对链表进行二分查找，不适合数据经常变化的数组。
1.二分查找
解题思路：数组有序 返回下标（查找元素）–> 二分法 这里采用左闭右闭区间[low,high]所以while判断的时候是low <= high
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
int low = 0;
int high = nums.length - 1;
int mid = (low + high)/2; // 向下取整
// int mid = low + （high - low） 这种也可以是为了防止溢出，
while(low <= high){
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
high = mid - 1;
class Solution {
public int searc mid = (low + high)/2;
}else{
low = mid + 1;
mid = (low + high)/2;
}
}
return -1;
}
}
|
2.二分查找插入点（无重复元素）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
犯的问题：粗心把high初始化的时候设置成 nums. length了，2，3，4情况返回值应该是high+1（要想明白为什么是high+1 ？–>2，3，4情况下，当循环终止时，high指向小于target的元素，low指向大于target的元素，因此插入的索引应该是high + 1）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public int searchInsert(int[] nums, int target) {
// 可能出现的情况四种1.找到nums[mid] = target
// 2.没出现 目标值在最前面
// 3.没出现 目标值在最后面
// 4.没出现 目标值在某个区间
// 2 3 4 要保证统一返回
int low = 0;
int high = nums.length - 1;
int mid = (high + low)/2;
while(low <= high){
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
high = mid - 1;
mid = (high + low)/2;
}else{
low = mid + 1;
mid = (high + low)/2;
}
}
return high + 1; // 注意这个是力扣上的题 是找到值就返回索引
}
}
|
二分查找插入点（有重复元素）
给定一个长度为 的有序数组 nums 和一个元素 target ，数组存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。**若数组中已存在元素 target ，则插入到其左方。**请返回插入后 target 在数组中的索引。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/* 二分查找插入点（存在重复元素） */
int binarySearchInsertion(int[] nums, int target) {
int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
while (i <= j) {
int m = i + (j - i) / 2; // 计算中点索引 m
if (nums[m] < target) {
i = m + 1; // target 在区间 [m+1, j] 中
} else if (nums[m] > target) {
j = m - 1; // target 在区间 [i, m-1] 中
} else {
j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
}
}
// 返回插入点 i
return i;
}
|
3.找起始位置和终止位置
没思路(老老实实写两个函数 不要想着函数复用和其他方法了 边界处理太难想了)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = searchLeft(nums, target);
int right = searchRight(nums, target);
if (left != -1 && right != -1) {
return new int[]{left, right};
}
return new int[]{-1, -1};
}
public int searchLeft(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] >= target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (low < nums.length && nums[low] == target) return low;
return -1;
}
public int searchRight(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] <= target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (high >= 0 && nums[high] == target) return high;
return -1;
}
}
|
移除元素
双指针：设计不同移动速度，不同间距，不同方向的两个指针进行操作 解决问题。指向相同序列一般有快慢指针，首尾指针，固定间距指针等。指向不同序列有归并排序。可以用来求链表的中点、链表是否成环、移除数组中多余的元素（原地移除）、归并排序 等
1.移除元素（快慢指针法）
思路：我一想到双指针脑子里面总是会想让i指向0，j指向i+1或者就是i指向0，j指向length-1.实际上的情况比这更复杂，不能用这种惯性思维来做题。（这道题是看了代码随想录的演示动画自己写的while循环 其实for循环比这个简单）
首先确定指针表示的含义 i是指向新的子数组的下标，新数组中不允许有val j是用于找到非val值用于交换的元素
初始化：i=j=0
在循环中i和j的变化分情况讨论 nums[i]！=val时 不需要交换 只需要i和j同时向后移动即可 nums[i]=val时
分两种情况 nums[j]=val时，需要让j自己移动到不为val的地方，变成nums[j]!=val的情况 然后进行交换 交换后i和j再同时移动
循环终止条件：当j到达length - 1 的时候循环终止
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
class Solution {
public int removeElement(int[] nums, int val) {
// i指针指向的数组中不允许有val j指针用于找到非val的元素
// 指针初始化位置 i=j=0
int i = 0;
int j = 0;
while(j <= nums.length - 1){
if(nums[i]==val){
if(nums[j]!=val){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j++;
}else{
j++;
}
}else{
i++;
j++;
}
}
return i;
}
}
// 第二种解法（推荐）
class Solution {
public int removeElement(int[] nums, int val) {
int i = 0;
int j = 0;
while(j<nums.length){
if(nums[j]!=val){
// 注意这个地方的执行顺序 如果先让i++ 然后再覆盖的话就会出现溢出错误 因为这是数组 i实际是个数字不是指针不会发生指针溢出的情况 如果让数组取nums[length]才会报错
nums[i] = nums[j];
i++;
}
j++;
}
return i;
}
}
|
2.26. 删除有序数组中的重复项 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public int removeDuplicates(int[] nums) {
int i = 0;//slow
int j = 0;//quick
while(j<nums.length){
if(nums[i]!=nums[j]){
i++;
nums[i] = nums[j];
}
j++; // 这一步是每次都会执行的，并不是执行完if语句就不执行了
}
return i+1;
}
}
|
date: 2025-10-19
283. 移动零 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public void moveZeroes(int[] nums) {
int i=0;
int j=0;
while(j<nums.length){
if(nums[j]!=0){
nums[i] = nums[j];
i++;
}
j++;
}
//比如初始数组是【1，0，2，0，3】 结束时数组是【1，2，3，0，3】所以需要对后面的进行赋零操作 要想清楚结束的时候i指向哪
while(i<nums.length){
nums[i] = 0;
i++;
}
}
}
|
977. 有序数组的平方 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public int[] sortedSquares(int[] nums) {
// 首尾双指针
int i = 0;
int j = nums.length-1;
int k = 0;
int[] nums2 = new int[nums.length];
while(i<=j){
if(nums[i]*nums[i] <= nums[j]*nums[j]){
nums2[k] = nums[i]*nums[i];
i++;
}else{
nums2[k] = nums[j]*nums[j];
j--;
}
k++;
}
Arrays.sort(nums2); // 无返回值 直接对原数组进行操作
return nums2;
}
}
|
209. 长度最小的子数组 - 力扣（LeetCode）
滑动窗口O（N）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// 第一种解法 时间复杂度和空间复杂度都是O(N) 使用了滑动窗口和动态数组 可以不用动态数组而是用一个变量来记录min_length
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int i = 0;
int sum = 0;
ArrayList<Integer> length_list = new ArrayList<>(); //
for(int j = 0;j< nums.length; j++){
sum += nums[j];
// 先大范围找 移动j 在满足粗略的条件之后再缩小范围 移动i【i和j都是只增不减的 双循环的时候j会变小】
while(sum >= target){
int length = j - i + 1;
length_list.add(length);
sum -= nums[i];
i++;
}
}
if(length_list == null || length_list.isEmpty()){
return 0;
}else{
int min_length = Collections.min(length_list);
return min_length;
}
}
}
|
59. 螺旋矩阵 II - 力扣（LeetCode）
主要是考察边界条件的判断
区间和: 可以用sum数组保存前n项和 如果想计算下标2-5的区间和 可以通过前5项和-前二项和
链表
—2025.10.20
链表节点类
1
2
3
4
5
6
7
|
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
|
链表删除节点 直接让next指针被删除节点的下一个节点即可 Java有自己的回收机制 被删除的节点会自动回收
关于链表的Java语法都忘完了 删除元素就是 current.next = current.next.next; 还需要注意什么时候创建的是节点 什么时候创建的是指针
203. 移除链表元素 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 设置一个虚拟头节点vir 以及一个当前指针cur用来遍历
ListNode vir = new ListNode();
vir.next = head; //vir放在head前面作为虚拟头节点
ListNode cur = vir; // cur指针指向当前遍历的节点
while(cur.next!=null){ //考虑清除循环终止条件 当cur遍历到最后一个节点 即cur.next == null 时终止循环
if(cur.next.val == val){
cur.next = cur.next.next; //如果cur指向的节点值为val 则移除
}else{
cur = cur.next; // 移动cur到下一个节点
}
}
// 返回值难以确定时 考虑极端情况试试
// 当首节点为val时 就会被删除 所以vir.next是正确的 而不是head
return vir.next;
}
}
|
707. 设计链表 - 力扣（LeetCode）
在链表类中还需要设置链表的size 和 head 以及初始化链表 最关键的就在于如何初始化 如何循环 以及如何结束循环
2025.10.21
206. 反转链表 - 力扣
反转链表（也不会 算法好难！！！–果然还是安静的时候写算法题有效果）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public ListNode reverseList(ListNode head) {
// 双指针
ListNode cur = head; // 当前节点指针
ListNode pre = null; // 当前节点指针的前一个节点
// （我想的太多了 我想着如果转换方向之后 后一个节点就找不到了 可以用临时temp记录一下就好了啊！）
while(cur != null){
ListNode temp = cur.next; // 记录一下当前节点的下一个节点的位置
cur.next = pre;
pre = cur; // 然后让pre向后移动 即指向cur
cur = temp; // 让cur指向temp
}
return pre;
}
}
|
24. 两两交换链表中的节点 - 力扣（LeetCode）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
//我想的是设置一个flag 来判断是否需要交换 然后用一个temp表示cur节点的后一个节点 用于交换 即在循环体中 1.temp = cur.next临时保存
// 2.cur.next->temp.next 3. temp.next->cur 但是有错误！！！ 2-1-3-5 4-3-5
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next ==null){ // 链表为空/链表中只有一个元素
return head;
}
// 这个代码是错误的 结果是2-1-3-5 4-3-5
ListNode cur = head;
while(cur.next !=null ){
ListNode temp = cur.next; // 这是用temp记录后一个节点不行 试试用temp记录pre
cur.next=temp.next;
temp.next=cur;
cur = cur.next;
}
return cur;
}
}
|
错误代码2：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next ==null){ // 链表为空/链表中只有一个元素
return head;
}
ListNode vir = new ListNode();
vir.next = head;
ListNode cur = head;
ListNode pre = vir;
while(cur.next !=null && cur.next.next!=null){
pre.next = cur.next;
cur.next = cur.next.next;
pre.next.next = cur;
pre = pre.next;
cur = cur.next;
}
return vir.next;
}
}
|
正确代码：
19 删除倒数第N个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
// 解题思路（Mine）：先找到这个节点是正数第几个位置 然后找到其前置节点 进行删除操作
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode vir = new ListNode();
vir.next = head;
ListNode cur = vir;
int size = 0;
// 遍历一遍得到链表的size
while(cur.next != null){
size++;
cur = cur.next;
}
int z = size - n + 2; //倒数第n是正数第size - n + 1 这里的z = size - n + 1是其前节点
ListNode vir2 = new ListNode();
vir2.next = head;
ListNode cur2 = vir2;
int count = 1; // 要注意这里的count是从1开始的 是指链表中的第几个节点
while(cur2.next != null){
count++;
if(count == z){
cur2.next = cur2.next.next;
return vir2.next;
}
cur2 = cur2.next;
}
return vir2.next;
}
}
|
面试题02.07链表相交
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
// 第一种方法（Mine），第二种方法用双指针
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 需要让长链先走 然后同步移动 看是否有节点相交
int A_size = 0; // A链表的长度
int B_size = 0; // B链表的长度
ListNode A_cur = headA;
ListNode B_cur = headB;
if(headA == null || headB==null){
return null;
}
while(A_cur != null){ //在计算链表长度的时候 循环条件里面是cur 不是cur.next
A_size++;
A_cur = A_cur.next;
}
while(B_cur != null){
B_size++;
B_cur = B_cur.next;
}
// 我想的是计算出A和B的长度差（用绝对值Math.abs(),但是这样还是区分不了哪个长哪个短）
// int length = Math.abs(A_size,B_size);
int length = 0;
ListNode slow = null; // 指向长链表的头节点
ListNode quick = null; // 指向短链表的头节点
if(A_size - B_size >= 0){
length = A_size - B_size;
quick = headA;
slow = headB;
}else{
length = -1 * (A_size - B_size);
quick = headB;
slow = headA;
}
// 将长链表的指针和短链表的指针同步
while(length > 0){
quick = quick.next;
length--;
}
while(quick != null){
// 注意这里不是quick.next 如果是这样 首节点都没有比较 如果设置了虚拟节点可以是vir.next
if(quick == slow){
return quick;
}
quick = quick.next;
slow = slow.next;
}
return null;
}
}
|
142 环形链表ii
如何判断一个链表中是否有环？ 快慢指针 fast 每次走两步 slow 每次走一步 最终会在环内相遇 fast会追上slow 因为在环内fast相当于每次都逼近slow一个节点
难点在于如何确定哪个节点是入环点！
【注意：链表中有些题目没有看别人优秀的题解 有些甚至都没做出来 显然下次遇到了 脑子里首先弹出来的还是自己不成熟的想法 没有形成一个自己的解题逻辑 这是不对的！应该吸收别人的思想为己所用】
Hash 表
哈希表可以快速判断一个元素是否出现在集合里 key-func（key）-value，但可能出现哈希冲突 不同的key映射到同一个value，解决方法：拉链法和线性探测法。 常见的哈希结构：数组，集合set，map。空间换时间。当遇到需要判断一个元素是否出现过 就要想到哈希法
242.有效的字母异位词