Leetcode：学习记录

一、滑动窗口

1. 找出数组中元素和大于给定值的子数组的最小长度

右指针从左到右遍历，在每个右指针下，如果去掉左边元素的元素和大于等于给定值则左指针右移一次，直到小于给定值，右指针右移一个。

2.找到乘积小于给定值的子数组的数量

右指针从左到右遍历，在每个右指针下，乘积大于等于给定值则左指针右移一次，直到小于给定值，右指针右移一个。

3.无重复字符的最长子串长度

右指针从左到右遍历，在每个右指针下，如果有重复左指针右移一次，直到没有重复，右指针右移一个。

二、二分法

1.在排序数组中查找元素的第一个和最后一个位置

红蓝染色法：查找第一个或最后一个或者小于等于或者小于或者大于给定值的第一个元素都可以转换成第一个大于等于给定值的问题。例如第一个等于给定值的元素，则是第一个大于等于给定值的元素，且等于给定值。大于等于给定值的元素，左指针右指针从两边开始，中间大于等于给定值则右指针变为中间，反之则左指针变为中间。

2.查找数组的峰值元素

红蓝染色法：峰值左侧红色，峰值右侧蓝色。L\M\R，M与右侧相比，如果大于右侧，那么右侧都是蓝色，如果小于那么左侧都是红色。

3.搜索旋转排序数组最小值

红蓝染色法：以最后一个元素为界可以区分两段，L\M\R中M小于最后一个元素，那么M就在右边一段，M的右侧就是蓝色，大于最后一个元素，M就在左边一段，M的左侧是红色。

三、链表

1.反转链表

遍历每个节点，cur为当前节点，cur的next保存为nxt后变为pre，pre变为cur，cur变为nxt，循环。即用完这个变量后再改变这个变量。

2.链表中间节点

快慢指针法：慢指针走一步，快指针走两步，快指针走到最后一个节点或者空节点时，慢指针就再中间节点。

3.环形链表

快慢指针法：慢指针走一步，快指针走两步，快指针相对来说走一步，那么如果存在环形链表，快指针必然会赶上慢指针。

4.重排链表

1和2结合，找到中间节点并翻转右侧部分，然后交叉。

5.删除链表某个节点

将该节点的值修改为下一个节点的值，该节点的next修改为下一个节点的next。

6.删除链表的倒数第N个节点

前后指针：前指针指向dummy node，后指针dummy node后移动n步。然后同步走，直到后指针为最后一个节点，然后删除前指针的后一个节点。

7.删除排序链表中的重复元素

如果下一个节点的值与当前节点相同，则删除下一个节点。