Leetcode（一）：数组、链表部分经典题目详解（JavaScript版）

提前声明：本博客内容均为笔者为了方便个人理解而发布，题目思路参考自代码随想录，如果大家有觉得写的不清晰的地方，欢迎在评论区提问。

一、数组

1. 二分查找

点击跳转到力扣题目

注意题目的前提条件：有序数组、无重复元素

解法：双指针

这道题目的难点在于边界的确定，[left,right]和[left,right)的边界处理是不一样的，前者right应该为nums.length-1，后者right应为nums.length。

第一种：左闭右闭，即从[left,right]区间搜索，以[1,2,3,4]，找1为例子带进去看看第一轮while循环

var search = function(nums, target) {let left = 0; //左指针闭区间，指向第一个位置0let right = nums.length - 1; //右指针闭区间，指向最后一个位置3//由于是左闭右闭，那么left=right就是有意义的，代表一直找到了最后一个元素while(left <= right) {let middle = Math.floor((right - left)/2) + left //寻找中间位置1//开始二分查找，不断缩小边界if(target < nums[middle]) {//缩小边界，由于right是闭区间，判断条件已经确定target<middle位置的值//由于是闭区间，下一次搜索一定会搜索<=middle-1处的值，right要变为middle-1=0right = middle - 1; } else if (target > nums[middle]) {left = middle + 1;//缩小边界，此时已确定target>middle位置的值，left要变为middle+1} else {return middle //如果中间位置这个数刚好对上，就返回，否则就会一直到循环的最后一轮}}//如果没有return，就return-1return -1
};

第一轮循环结束后，搜索区间变成了[0,0]，也就是左右指针都指向了位置0的元素1，此时左右指针相撞，left=right就是有意义的，所以while循环的条件就是<=，等于号的情况代表一直找到了最后一个元素

第二种：左闭右开，即从[left,right)区间搜索，以[1,2,3,4]，找1为例子带进去看看第一轮while循环

var search = function(nums, target) {let left = 0; //左指针闭区间，指向第一个位置0let right = nums.length; //右指针开区间，指向最后一个位置3的后面4//由于是左闭右开，那么left=right就是没有意义的while(left < right) {let middle = Math.floor((right - left)/2) + left //寻找中间位置1//开始二分查找，不断缩小边界if(target < nums[middle]) {//缩小边界，由于right是开区间，判断条件已经确定target<middle位置的值//由于是开区间，下一次搜索一定会搜索<middle的值，right要变为middle=1right = middle; } else if (target > nums[middle]) {//缩小边界，由于left是闭区间，判断条件已经确定target>middle位置的值//由于是闭区间，下一次搜索一定会搜索>=middle+1的值，left要变为middle+1	       left = middle + 1;} else {return middle //如果中间位置这个数刚好对上，就返回，否则就会一直到循环的最后一轮}}//如果没有return，就return-1return -1
};

第一轮循环结束后，搜索区间变成了[0,1)，也就是左指针指向了位置0的元素1，右指针指向了位置1的元素2，此时必然会锁定0位置的元素，所以while循环的条件就是<。

这个题有点不太好描述，感觉容易乱，先这样吧……我觉得最好按第一种方法来记

2. 移除数组元素

点击跳转到力扣题目
做这道题必须要知道数组的特点，那就是删除元素时只能覆盖，不是原地删除

解法：快慢指针法

想要用快慢指针法解这个问题，最关键的点就是理解slow和fast都代表什么
我们可以把慢指针理解为新数组的每个位置，快指针的作用是遍历整个数组，这样的话快指针只需要找到不用删除的元素，然后依次覆盖就可以了。
可以仔细看下注释，以removeElement([1,2,3,4],3)理解一下指针的移动过程

var removeElement = function(nums, val) {let slow = 0; //慢指针，指向新数组的每个位置for(let fast = 0; fast < nums.length; fast++) { //快指针fast遍历数组if(nums[fast] !== val) {    //如果快指针指向的不是要删除的元素，那么就让快指针位置的值覆盖慢指针位置的值nums[slow] = nums[fast]slow++ //然后慢指针先移动，快指针再移动}//如果是要删除的元素，那么只有快指针移动（fast++），慢指针不动//这样可以做到后面的值覆盖到当前慢指针指向的位置}//移除后数组长度，就是当前slow指向的这个索引return slow //因为如果覆盖了当前元素，slow会先往后移，此时指向的是没有元素的位置//比如[1,2,3,4]，删除3时，slow指向3，fast指向4，4覆盖3后slow指向4，此时索引为3，正好是数组长度
};

3. 有序数组的平方

点击跳转到力扣题目

解法：双指针法

这个题目相较于前面两个，更好理解一些，其实也可以先平方再快排，但是更好的是用空间换时间，使用双指针法，依次找最大的元素unshift，当两个指针相撞时，就是最小的那个元素。

//双指针法，空间换时间，时间复杂度O(N)var sortedSquares = function(nums) {let i = 0;   //一个指针指向头部let j = nums.length - 1;  //一个指针指向尾部let result = []; //开辟一个新的空间//注意循环停止的条件，当i = j时，指针相撞，指向的应该是最小的元素，循环应继续while(i<=j) {let left = Math.pow(nums[i],2)let right = Math.pow(nums[j],2)if( left > right) {result.unshift(left)i++} else {result.unshift(right)j--}}return result
};

4. 长度最小的子数组

点击跳转到力扣题目

解法：暴力or滑动窗口

这道题目其实也可以用暴力求解，那就是双重for循环把所有可能的长度组合枚举出来，然后去找哪个是满足条件的长度最小子数组，并返回它的长度。

var minSubArrayLen = function(target, nums) {let result = Number.MAX_VALUE; //获取已知的最大值//外层循环，以每一个元素作为起点去找目标值for(let i = 0; i < nums.length; i++) {let sum = 0;//内层循环，寻找目标值for(let j = i; j < nums.length; j++) {sum += nums[j];if (sum >= target) {result = Math.min(result, j - i + 1); //和上一个长度比较，取较小的值break;}}}// 如果最后result没变化，那么说明没有比target大的组合return result === Number.MAX_VALUE ? 0 : result;
};

这里有很妙的一个方法，可以把时间复杂度降低到O(n)：

为了方便理解，直接以target = 101, nums = [1,1,1,100,1]为例，走一遍下面的逻辑
滑动窗口：先确定终止的位置（因为如果先确定开始位置，那么终止位置的确定和暴力解法就一样了），确定的方式就是去遍历数组，找到第一个符合sum >= target的位置，作为第一个滑动窗口的终止位置，开始位置直接从0开始，然后第一个符合条件的长度就是 j - i + 1 此时窗口开始缩短（i向前移动），移动前要先把之前位置的数值从sum中删掉。之后一直循环直到条件不成立，则j开始移动，就这样不断滑动，可以过一遍所有可能的情况。

为什么时间复杂度是O(n)呢？因为每个元素只被过了2次，那就是O(2n)，也就是O(n)

var minSubArrayLen = function(target, nums) {let result = Number.MAX_VALUE; //找到最大值，方便下面对result进行取小let sum = 0; //初始化sumlet i = 0; //开始位置是第一个for(let j = 0; j < nums.length; j++) {sum = sum + nums[j]; //通过前几次循环，先找到符合条件的j值，作为滑动窗口终止位置while (sum >= target) { //i开始移动result = Math.min(result, j - i + 1) //如果目标长度比上一个小，就替换一下子sum = sum - nums[i]; //替换之后，i继续蠢蠢欲动，移动前，先把旧i位置的值从sum删掉i++; //窗口左侧开始滑动，看一下下一个值是否是符合条件的值，如果是，则继续循环移动开始位置}}return result === Number.MAX_VALUE ? 0 : result;
};

5. 螺旋矩阵

点击跳转到力扣题目

这道题的难点在于各种边界的确定，我们需要哪些状态来协助我们进行数组的更新。

1. 第一个能想到的状态是count，因为要记录每次要填的数，每填一个就++
2. 第二个就是每一圈x轴和y轴的坐标，第一圈从00开始，第二圈从11开始
3. 第三个就是要转几圈，通过循环填充数字，那么转几圈是很重要的，偶数就是n/2圈，奇数则是向下取整圈，比如3那就转1圈，中间的数字单独考虑，5则转两圈，中间的数组单独考虑
4. 第四个就是填充的时候这个偏移量offset，每一圈开始和结束的位置是不一样的，比如第一圈的第一行是从startX=0开始，到n-1结束，第二圈的第一行是从startX=1开始，到n-2结束的，所以offset每轮都要递增一下
5. 仔细看下注释，你会明白的

var generateMatrix = function(n) {//1.初始化各种需要的变量，其中二维数组所有元素补0（因为js中无法直接通过索引添加元素）let result = new Array(n).fill(0).map(() => new Array(n).fill(0));let count = 1; //从1开始计数，一直到n，依次填充到n方let startX = 0; //初始化每一圈的x轴坐标let startY = 0; //初始化每一圈的y轴坐标let loop = Math.floor(n/2); //转几圈let offset = 1;//每一个while就是转一圈，转几圈取决于是奇数还是偶数，偶数就是n/2圈，奇数则最后一圈不转，单独填充下就行了while(loop > 0) {let row = startX; //初始化每一圈的行坐标let col = startY; //初始化每一圈的列坐标//填充上行从左到右，左闭右开，临界值是n-offsetfor(; col < n - offset; col++) {result[row][col] = count;count++;}//此时col停在了右列，row开始移动//填充右列从上到下for(; row < n - offset; row++) {result[row][col] = count;count++;}//此时row停在了下列，col开始移动//填充下行从右到左for(; col > startX; col--) {result[row][col] = count;count++;}//此时col停在了左列，row开始移动//填充左列从下到上for(; row > startY; row--) {result[row][col] = count;count++;}loop--; //每转完一圈，loop减1startX++; //每转完一圈，开始位置要移动，为下一圈做准备startY++; //每转完一圈，开始位置要移动，为下一圈做准备offset++; //每转完一圈，填充的临界值（n-offset）都要缩小}//如果是奇数n，那么需要单独给矩阵中间的位置赋值，索引就是迭代到最后一圈时x和y轴的坐标位置if (n % 2 === 1) {result[startX][startY] = count}return result;
};

二、链表

1. 删除链表元素

点击跳转到力扣题目

解法：添加虚拟头节点，双指针

这个其实比较简单，方法是添加一个虚拟头节点，然后删除时，让上一个节点的next指向当前节点的next就可以了：

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @param {number} val* @return {ListNode}*/
var removeElements = function(head, val) {let dummyHead = new ListNode(0, head) //创建一个虚拟头节点let pre = dummyHead //指针1，指向虚拟头节点let current = head //指针2，指向头节点//循环移动指针，一直到current指向null，所有链表元素遍历完毕while(current) {if(current.val === val) {//如果找到要删除的元素pre.next = current.next //pre指向current后面，这样被跳过的元素会被自动回收current = current.next //指针current移动} else {//否则，移动两个指针继续寻找pre = currentcurrent = current.next}}return dummyHead.next
};

2. 设计链表

点击跳转到力扣题目

这里其实不需要虚拟头节点，我没有用虚拟头节点，双指针pre默认为null，current默认为第一个节点，然后依次迭代

几个注意点：1.不用虚拟头节点 2.插入删除到0位置时单独判断 3.小心空指针情况（比如尾部插入时）

class LinkNode {constructor(val) {this.val = val;this.next = null;}
}var MyLinkedList = function() {this.head = null;this.size = 0;
};/** * @param {number} index* @return {number}*/
MyLinkedList.prototype.get = function(index) {if(index < 0 || index > this.size - 1) return -1;let current = this.head;for(let i = 0; i < index; i++) {current = current.next}return current.val;
};/** * @param {number} val* @return {void}*/
MyLinkedList.prototype.addAtHead = function(val) {const Node = new LinkNode(val);Node.next = this.head;this.head = Node;this.size++;
};/** * @param {number} val* @return {void}*/
MyLinkedList.prototype.addAtTail = function(val) {const Node = new LinkNode(val);let current = this.head;if(this.head) {while(current.next) {current = current.next;}current.next = Node;} else {this.head = Node;}this.size++;
};/** * @param {number} index * @param {number} val* @return {void}*/
MyLinkedList.prototype.addAtIndex = function(index, val) {if(index < 0 || index > this.size) return falseconst Node = new LinkNode(val);let pre = null;let current = this.head;for(let i = 0; i < index; i++) {pre = current;current = current.next;}if(index === 0) {Node.next = this.head;this.head = Node;} else {pre.next = Node;Node.next = current;}this.size++;
};/** * @param {number} index* @return {void}*/
MyLinkedList.prototype.deleteAtIndex = function(index) {if(index < 0 || index > this.size - 1) return falselet pre = null;let current = this.head;for(let i = 0; i < index; i++) {pre = current;current = current.next;}if(index === 0) {this.head = current.next} else {pre.next = current.next}this.size--;
};/*** Your MyLinkedList object will be instantiated and called as such:* var obj = new MyLinkedList()* var param_1 = obj.get(index)* obj.addAtHead(val)* obj.addAtTail(val)* obj.addAtIndex(index,val)* obj.deleteAtIndex(index)*/

3.反转链表

点击跳转到力扣题目

解法1：双指针迭代

双指针迭代就是定义两个指针pre和current，依次改变指针的指向，具体看下面的代码和注释：

function reverseList(head) {let pre = null;  //定义一个空指针在head的前面let current = head;  //定义另一个指针指向头节点while(current) {    //current指针为空的时候说明指到尾节点了，就停止循环let temp = current.next;  //定义一个temp来保存当前节点的下一个节点current.next = pre;  //关键一步，改变指针指向，把向后指的指针改为向前指pre = current;    //pre指针向后移，指向currentcurrent = temp;   //current指针向后移，指向当前节点的下一个节点（提前保存了）}return pre;   //最后返回新的头指针（current指向了null）
}

解法2：递归

递归的实现思路和双指针迭代是类似的，也是要有两个指针向后指

function reverseList(head) {return reverse(null,head); //初始 pre = null, current = head
}//定义递归函数，作用其实就是让指针向后移
function reverse(pre,current) {     //定义两个指针，一个pre指向前面，一个current指向当前if(current == null) return pre; //递归停止的条件（最后一层递归开始出栈,返回头指针）let temp = current.next;  //保存后面的节点，方便后面让指针向后移current.next = pre;  //改变指向return reverse(current,temp);  //返回一个递归的调用
}

4.两两交换链表中的节点

点击跳转到力扣题目

 /*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @return {ListNode}*/
var swapPairs = function(head) {//1.创建虚拟头节点const dummyhead = new ListNode(0);dummyhead.next = head;//2.创建双指针let pre = dummyhead;let current = head;//3.奇数和偶数项的结束条件，先判断current有没有，再判断curren.next有没有（逻辑中断）while(current && current.next) {//4.依次改变指针指向，注意不要出现空指针的情况let temp = current.next; //测试中发现current.next会丢失，先保存一下//4.1调转两个节点pre.next = temp; current.next = temp.next;temp.next = current;//4.2指针向后移动pre = current;current = current.next;}//综上如果无法在脑中模拟，画个图其实就明白了return dummyhead.next;
};

5.删除链表倒数第n个节点

点击跳转到力扣题目

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @param {number} n* @return {ListNode}*/
var removeNthFromEnd = function(head, n) {//使用头节点就是为了：不需要单独考虑删除头节点的情况const dummyhead = new ListNode(0);dummyhead.next = head;//快慢指针法let fast = dummyhead;let slow = dummyhead;n = n + 1;//快指针先走n+1下，慢指针不动while(n-- > 0) {fast = fast.next;}//快慢指针一起移动，当快指针指向null时，慢指针指向的就是要删除的节点的前一个节点，仔细想想是不是while(fast) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;//这里返回的不能是head，因为如果删除的是head，那么dummyhead指针指向了第二个节点//但此时head还是有值的，通过head仍然能获取链表所有值，相当于head并没有被删掉（仔细想想删除头节点时指针的改变）return dummyhead.next; 
};

6.环形链表

先占个坑