大厂算法面试之 leetcode 精讲 7. 双指针
搞定大厂算法面试之 leetcode 精讲 7.双指针
视频教程(高效学习):点击学习
目录:
双指针
普通指针:两指针同一方向或不同方向
对撞指针:两指针互相靠拢
快慢指针:一快一慢
141. 环形链表 (easy)
方法 1.哈希表或 set:
思路:准备一个 map 或者 set,然后循环链表,每次遍历到一个节点的时候,判断当前节点是否在 map 中存在,如果不存在就把当前节点加入 map 中,如果存在的话说明之前访问过此节点,也就说明了这条链表有环。
复杂度分析:时间复杂度
O(n)
,n 是链表的数量,最差的情况下每个节点都要遍历。空间复杂度O(n)
,n 是存储遍历过的节点的 map 或者 set
js:
java:
方法 2.快慢指针
思路:准备两个指针 fast 和 slow,循环链表,slow 指针初始也指向 head,每次循环向前走一步,fast 指针初始指向 head,每次循环向前两步,如果没有环,则快指针会抵达终点,如果有环,那么快指针会追上慢指针
复杂度:时间复杂度
O(n)
,空间复杂度O(1)
js:
java:
142. 环形链表 II (medium)
方法 1.哈希表
思路:遍历链表,将节点加入一个 set 中,每次判断当前节点是否在 set 中,如果存在重复的节点,这个节点就是入环节点
复杂度:时间复杂度
O(n)
,空间复杂度O(n)
js:
java:
方法 2.快慢指针
思路:慢指针移动两步,快指针移动一步,相遇之后,快指针变成头指针,然后每次快慢指针各走一步直到相遇,相遇的节点就是入环节点
复杂度:时间复杂度
O(n)
,空间复杂度O(1)
js:
java:
15. 三数之和 (medium)
方法 1.暴力求解,对于三个数字,循环 3 次,分别计算和,时间复杂度O(n^3)
方法 2.c=-(a+b): 确定了 a 和 b,那就可以想两数之和一样,在 map 中寻找-(a+b)
,减少一层循环,时间复杂度O(n^2)
,空间复杂度O(n)
。
方法 3.排序然后查找
思路:先排序数组,数组长度必须大于 3,循环数组,假如当前循环到了 i 索引,则定义两个指针
L = i+1
,和R = nums.length-1
,如果和sum=nums[i] + nums[L] + nums[R]
小于 0,则向右移动左指针,如果 sum 大于 0,则左移右指针,如果 sum 等于 0,则正好找到了这 3 个数,然后在尝试L++
,R--
,继续寻找中间是否有三个数之和等于 0,注意在循环的过程中遇见相同的三个数需要去重。复杂度分析:时间复杂度
O(n^2)
,n 为数组的长度。空间复杂度O(logn)
,即排序所需要的空间
js:
java:
11. 盛最多水的容器 (medium)
方法 1:双指针
思路:用双指针 i,j 循环 height 数,i,j 对应高度较小的那个先向内移动,不断计算面积,更新最大面积
复杂度:时间复杂度
O(n)
,n 是数组 height 的长度,遍历一次。空间复杂度O(1)
js:
java:
160. 相交链表 (easy)
方法 1:哈希表
思路:将链表 A 存入 set 中,第一个相同的节点就是重合的节点
复杂度:时间复杂度
O(m+n)
,m、n 分别是两个链表的长度。空间复杂度O(m)
js:
Java:
方法 2:双指针
思路:用双指针 pA 、pB 循环俩个链表,链表 A 循环结束就循环链表 B,链表 A 循环结束就循环链表 B,当
pA == pB
时就是交点,因为两个指针移动的步数一样复杂度:时间复杂度
O(m+n)
,m、n 分别是两个链表的长度。空间复杂度O(1)
js:
java:
876. 链表的中间结点(easy)
思路:快慢指针遍历,直到快指针到达最后
复杂度:时间复杂度
O(n)
,空间复杂度O(1)
js:
java:
评论