双指针是解数组类型题的最常见解法。

  • 比如有头尾分别有指针，然后依次向中间靠拢
  • 还有一种是快慢指针，两个指针都从左边起，一个走的快，一个走得慢

删除数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

  1. 说明:
  3. 为什么返回数值是整数，但输出的答案是数组呢?
  5. 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
  7. 你可以想象内部操作如下:
  9. // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
  10. int len = removeDuplicates(nums);
  12. // 在函数里修改输入数组对于调用者是可见的。
  13. // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
  14. for (int i = 0; i < len; i++) {
  15.     print(nums[i]);
  16. }
  1. 示例 1：
  2. 输入：nums = [1,1,2]
  3. 输出：2, nums = [1,2]
  4. 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
  6. 示例 2：
  7. 输入：nums = [0,0,1,1,1,2,2,3,3,4]
  9. 输出：5, nums = [0,1,2,3,4]
  10. 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

这题在题目要求上有限制，就是你可以改变nums里的元素的值，却不能对nums进行重新赋值。
而且返回的数字n，就代表了 nums 前n项，也就是数组里所有的不重复项。

  1. // 如果没有不允许对nums赋值的要求，可以用for循环
  2. // 两轮循环，相同元素则把元素改为undefined，不同元素则更新i的值
  3. var removeDuplicates = function(nums) {
  4.   for (let i = 0; i < nums.length; i++) {
  5.     for (let j = i+1; j < nums.length; j++) {
  6.       if (nums[i] === nums[j]) {
  7.         nums[j] = undefined 
  8.       } else {
  9.         i = j
  10.         break
  11.       }
  12.     }
  13.   }
  14.   nums = nums.filter(e => e) // 过滤掉undefined的元素 （可惜不满足题意）
  15.   return nums.length
  16. };

这道题目的就是让你，把数组的前n位元素，改成数组里所有不重复的元素值。
双指针法：
让两个指针快慢不同的向右移动
image.png

  • 慢指针是i，快指针是j
  • 如果nums[i] 等于 nums[j] 说明是相同的元素，j继续走，i还在原位
  • 如果nums[i] 不等于 nums[j] 说明是不相同的元素，那么nums[i++] = nums[j]，j继续向前走
    1. /**
    2. * @param {number[]} nums
    3. * @return {number}
    4. */
    5. var removeDuplicates = function (nums) {
    6. let i = 0;
    7. for (let j = 1; j < nums.length; j++) {
    8.     if (nums[j] !== nums[i]) {
    9.       nums[++i] = nums[j] // 先+再用。因为不是要更新nums[i], 而是要更新当前位的下一位。同时i也要递增1
    10.   }
    11. }
    12. return i+1 // length，要加1
    13. }

    合并两个有序数组

    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
    请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
    注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
  1. 示例 1：
  2. 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
  3. 输出：[1,2,2,3,5,6]
  4. 解释：需要合并 [1,2,3] 和 [2,5,6] 。
  5. 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
  7. 示例 2：
  8. 输入：nums1 = [1], m = 1, nums2 = [], n = 0
  9. 输出：[1]
  10. 解释：需要合并 [1] 和 [] 。
  11. 合并结果是 [1] 。
  13. 示例 3：
  14. 输入：nums1 = [0], m = 0, nums2 = [1], n = 1
  15. 输出：[1]
  16. 解释：需要合并的数组是 [] 和 [1] 。
  17. 合并结果是 [1] 。
  18. 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

方法一： 首先用js的排序肯定是可以的, 但是排序算法的时间复杂度会比较高

  1. var merge = function(nums1, m, nums2, n) {
  2.     nums1.splice(m, nums.length-1, ...nums2) // 把nums1 后面的0 切割掉，换成nums2里的元素
  3.   nums1.sort((a, b) => a - b)
  4. }

方法二：新建一个数组，然后分别比较两个数组元素的大小。
我自己写的这个其实用的也是双指针法：
双指针套路 （8题） - 图2

  2. /**
  3.  * @param {number[]} nums1
  4.  * @param {number} m
  5.  * @param {number[]} nums2
  6.  * @param {number} n
  7.  * @return {void} Do not return anything, modify nums1 in-place instead.
  8.  */
  9. var merge = function(nums1, m, nums2, n) {
  10.   const arr = []
  11.   let i = 0;
  12.   let j = 0;
  13.   while (i < m || j < n) { // 只要没有全都走完，就继续
  14.     if (i >= m) { // nums1 m之后的元素都是占位元素，不参与比较
  15.       arr.push(nums2[j])
  16.       j++
  17.       continue // 跳出本次循环，继续下次循环
  18.     }
  19.     if (j >= n) {
  20.       arr.push(nums1[i])
  21.       i++
  22.       continue
  23.     }
  24.     // 谁小谁的指针向右移
  25.     if (nums1[i] > nums2[j]) {
  26.       arr.push(nums2[j])
  27.       j++
  28.     } else {
  29.       arr.push(nums1[i])
  30.       i++
  31.     }
  32.   }
  33.   // arr就是排序后的数组
  34.   // 题目要求是直接改变 nums1,所以替换nums1 元素
  35.   for (let n = 0; n < arr.length; n++) {
  36.       nums1[n] = arr[n]
  37.   }
  38. };

上面的方法里还是使用了临时变量，因为如果直接操作nums1，那nums1中元素会在取值前被覆盖。其实这题里nums1 后面一部分的元素是用来占位的，就是用来存放元素的。
仍旧使用双指针法，但是从尾部开始向头部进行遍历
双指针套路 （8题） - 图3

  1. // 双指针法，从后往前
  2. var merge = function(nums1, m, nums2, n) {
  3.   let i = m - 1;
  4.   let j = n - 1;
  5.   let p = nums1.length - 1
  6.   while (p >= 0) {
  7.     if (i < 0) {
  8.       nums1[p--] = nums2[j--] // 注意这里的p-- 和 j--, 偷懒写法，先使用p的值， 然后p = p - 1
  9.       continue // 记得要跳出本次循环
  10.     }
  11.     if (j < 0) {
  12.       nums1[p--] = nums1[i--]
  13.       continue
  14.     }
  15.     if (nums1[i] > nums2[j]) {
  16.       nums1[p--] = nums1[i--]
  17.     } else {
  18.       nums1[p--] = nums2[j--]
  19.     }
  20.   }
  21. }

验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

  1. 示例 1:
  3. 输入: "A man, a plan, a canal: Panama"
  4. 输出: true
  5. 解释："amanaplanacanalpanama" 是回文串
  6. 示例 2:
  8. 输入: "race a car"
  9. 输出: false
  10. 解释："raceacar" 不是回文串

解题思路就是俩指针从两边向中间靠拢。注意要把输入的字符串处理下。

  1. /**
  2.  * @param {string} s
  3.  * @return {boolean}
  4.  */
  5. var isPalindrome = function(s) {
  6.   const str = s.replace(/(\W|_)/g, '').toLowerCase()
  7.   let p1 = 0
  8.   let p2 = str.length - 1
  9.   while(p2 >= p1) {
  10.     if (str[p1] !== str[p2]) return false
  11.     p1++
  12.     p2--
  13.   }
  14.   return true
  15. };

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：
image.png
输入：head = [1,2,2,1] 输出：true

示例 2：
image.png
输入：head = [1,2] 输出：false

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

  1. /**
  2.  * @param {ListNode} head
  3.  * @return {boolean}
  4.  */
  5. // 方法一，将链表变数组，判断数组是否是对称的
  6. var isPalindrome = function(head) {
  7.   const arr = []
  8.   while (head) {
  9.     arr.push(head.val)
  10.     head = head.next
  11.   }
  12.   let p1 = 0
  13.   let p2 = arr.length - 1
  14.   while (p1 <= p2) {
  15.     if (arr[p1] !== arr[p2]) return false
  16.     p1++
  17.     p2--
  18.   }
  19.   return true
  20. };

这种方法开辟了个数组，空间复杂度O(n)，这题也可以使用快慢指针的方式。

首先，我们要找到链表的中间点，然后对后半部分进行反转。再比较前半部分和反转后的部分是否节点值一致。
那么该如何找到中间节点呢？
可以遍历完链表，得知链表中有多少个个节点，记录下，然后一直next到中间节点的位置。这样有点麻烦。

为了获取中间节点，可以使用两个指针，一个一次走一步，一个一次走两步，这样当走两步的到达结尾（不一定是最后一个节点）时，走一步的正好在中间位置。 （同样的方法，可以获取链表或数组 的 1/2、3/1、1/4位置的节点）

  1. // 获取中间节点
  2. const getMidNode = function (head) {
  3.   let fast = head
  4.   let slow = head
  5.     while(fast.next !== null && fast.next.next !== null) { // 注意这里的判断，fast.next 和 fast.next.next存在，保证fast还没有到结尾。有fast.next 没有fast.next.next，说明是偶数个节点的链表
  6.     fast = fast.next.next
  7.     slow = slow.next
  8.   }
  9.   return slow
  10. }

注意链表这种结构的特征，每一个next，都是相当于后面整个链表的。 next -> next -> next -> …… next里存放的是下一个节点对象的内存地址。
如果说 链表1中某个节点 === 链表2中的某个节点， 说明这俩节点后的链表是同一条。就像车道汇合。

拿到了链表的中间节点， 那么就从中间节点开始，反转从中间节点之后的链表部分。 反转链表之前有过的
反转链表这个其实也像是快慢指针的形式
双指针套路 （8题） - 图6

  1. // 反转链表
  2. const reverseList = function (listNode) {
  3.     let prev = null
  4.   let head = listNode
  5.   while (head) {
  6.       const next = head.next
  7.     head.next = prev
  8.     prev = head // 往后移
  9.     head = next // 往后移
  10.   }
  11.   return prev
  12. }

现在已经得到了反转后的链表了，那就开始比较两个链表的节点值是不是相等。
注意，这里比较的是原始链表，和 后半部分反转后的链表，只需要当遍历完后半部分就可以结束了。

  1. var compare = function (n1, n2) {
  2.     while (n2) {
  3.       if (n1.val !== n2.val) return false
  4.     n1 = n1 ? n1.next : null
  5.     n2 = n2 ? n2.next : null
  6.   }
  7.   return true
  8. }

因为前面我们改变过原链表的后半部分，最好还是还原一下

  1. var isPalindrome = function(head) {
  2.   if (head === null) return true
  3.   const halfListNode = getMidNode(head)
  4.   const lastHafListNode = reverseList(halfListNode.next)
  5.   const result = compare(head, lastHafListNode) // 先执行
  6.   halfListNode.next = reverseList(lastHafListNode) // 再还原原链表
  7.   return result
  8. }

所以完整流程就是
进阶版

  1. // 1. 获取中间节点。 知识点： 快慢指针找中间点
  2. const getMidNode = function (head) {
  3.   let fast = head
  4.   let slow = head
  5.     while(fast.next !== null && fast.next.next !== null) { // 注意这里的判断，fast.next 和 fast.next.next存在，保证fast还没有到结尾。有fast.next 没有fast.next.next，说明是偶数个节点的链表
  6.     fast = fast.next.next
  7.     slow = slow.next
  8.   }
  9.   return slow
  10. }
  11. // 2. 反转链表。 知识点： 双指针
  12. const reverseList = function (listNode) {
  13.     let prev = null
  14.   let head = listNode
  15.   while (head) {
  16.       const next = head.next
  17.     head.next = prev
  18.     prev = head // 往后移
  19.     head = next // 往后移
  20.   }
  21.   return prev
  22. }
  23. // 3. 俩链表比较。知识点：迭代
  24. var compare = function (n1, n2) {
  25.     while (n2) {
  26.       if (n1.val !== n2.val) return false
  27.     n1 = n1 ? n1.next : null
  28.     n2 = n2 ? n2.next : null
  29.   }
  30.   return true
  31. }
  32. // 4.判断回文。 知识点：要先执行compre，然后再执行 halfListNode.next = , 否则 lastHafListNode 的值会变化。 变量lastHafListNode中保存的都是对象的引用地址
  33. var isPalindrome = function(head) {
  34.   if (head === null) return true
  35.   const halfListNode = getMidNode(head)
  36.   const lastHafListNode = reverseList(halfListNode.next)
  37.   const result = compare(head, lastHafListNode) // 先执行
  38.   halfListNode.next = reverseList(lastHafListNode) // 再还原原链表
  39.   return result
  40. }

上述过程分成了4步骤，还是稍显麻烦，有没有更简洁一点的办法呢？
其实在找中间点 和 反转链表的过程 可以合并在一起，在找的过程中，将前半部分反转了，然后跟后半部分比较

进阶pro版

  1. var isPalindrome = function(head) {
  2.     let slow = head
  3.   let fast = head
  4.   let prev = null
  5.   while (fast && fast.next ) {
  6.       fast = fast.next.next; // 一次走两步
  7.     [slow.next, slow, prev ] = [prev, slow.next, slow]; // //在前半个循环中找到中间，并且慢指针顺手将所过地区翻转
  8.   }
  9.   //出了while，fast或者fast.next已经null了，且前半段已经反转，下面 slow pre 开始配合 
  10.   if (fast) slow = slow.next
  11.   // 比较slow 和 prev， slow是后半段，prev是反转后的前半段
  12.   while(slow) {
  13.       if (prev.val !== slow.val) return false
  14.     prev = prev.next
  15.     slow = slow.next
  16.   }
  17.   return true
  18. }

删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
现有一个链表 — head = [4,5,1,9]，它可以表示为:
image.png

  1. 示例 1：
  3. 输入：head = [4,5,1,9], node = 5
  4. 输出：[4,1,9]
  5. 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
  6. 示例 2：
  8. 输入：head = [4,5,1,9], node = 1
  9. 输出：[4,5,9]
  10. 解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
  13. 提示：
  15. 链表至少包含两个节点。
  16. 链表中所有节点的值都是唯一的。
  17. 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  18. 不要从你的函数中返回任何结果。

这道题只给了一个参数，就是被删除的节点。 可能第一反应是，我应该知道这个链表的前一个节点啊，然后
prev.val = prev.next.next.val
prev.next = rev.next.next
这样就越过了当前的这个节点。但是没给链表 这个参数，怎么越过当前节点呢？
但是一个节点里有两个信息，val 和next， 只要将当前节点的val 和next 修改成别的了，那么当前节点其实就可以看成是不存在的了。
所以解法很简单。

  1. /**
  2.  * @param {ListNode} node
  3.  * @return {void} Do not return anything, modify node in-place instead.
  4.  */
  6. var deleteNode = function(node) {
  7.     node.val = node.next.val
  8.     node.next = node.next.next
  9. };

移动0

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

  1. 示例:
  3. 输入: [0,1,0,3,12]
  4. 输出: [1,3,12,0,0]
  6. 说明:
  7. 必须在原数组上操作，不能拷贝额外的数组。
  8. 尽量减少操作次数。

思路： 这道题跟前面的 合并两个有序数组 是类似的，也是双指针解法。
快慢两个指针，如果快指针指向的元素不为0， 而慢指针为0， 则交换两个元素的位置，并且将快慢指针都向后移动一位。
只不过快指针在每次迭代的时候都往后移动，而慢指针只在 快指针不为0慢指针为0 和 慢指针本身不为0 的情况下向右移动1位。
image.png

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {void} Do not return anything, modify nums in-place instead.
  4.  */
  5. var moveZeroes = function(nums) {
  6.   let i = 0;
  7.   let j = 1;
  8.   while(j < nums.length) {
  9.     if (nums[j] !== 0 && nums[i] === 0) {
  10.       [nums[j], nums[i]] = [nums[i], nums[j]]
  11.       i++
  12.     } else if (nums[i] !== 0) {
  13.       i++
  14.     }
  15.     j++
  16.   }
  17. };
  19. // 其实if 和 else if可以合并下
  20. // 但是一旦这么写，要注意i和j都是从0开始的。
  21. // 这样就避免 原始数组[1,2] 被改成了 [2,1]的问题
  22. var moveZeroes = function(nums) {
  23.   let i = j = 0;
  24.   while(j < nums.length) {
  25.       if(nums[j] !== 0){
  26.           [nums[i], nums[j]] = [nums[j], nums[i]]
  27.           i++
  28.       }
  29.       j++
  30.   }
  31.   return nums
  32. };

反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

  1. 示例 1：
  3. 输入：["h","e","l","l","o"]
  4. 输出：["o","l","l","e","h"]
  5. 示例 2：
  7. 输入：["H","a","n","n","a","h"]
  8. 输出：["h","a","n","n","a","H"]

经过了前面几题的训练，这种已经很简单了。双指针，一个从头，一个从尾， 交换位置。

  1. var reverseString = function(s) {
  2.   let i = 0;
  3.   let j = s.length - 1;
  4.   while (i <= j) {
  5.     [s[i], s[j]] = [s[j], s[i]];
  6.     i++;
  7.     j--
  8.   }
  9. };

两个数组的交集2

给定两个数组，编写一个函数来计算它们的交集。

  1. 示例 1：
  3. 输入：nums1 = [1,2,2,1], nums2 = [2,2]
  4. 输出：[2,2]
  5. 示例 2:
  7. 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  8. 输出：[4,9]
  11. 说明：
  13. 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
  14. 我们可以不考虑输出结果的顺序。
  15. 进阶：
  17. 如果给定的数组已经排好序呢？你将如何优化你的算法？
  18. 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
  19. 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

判断交集。。其实最先应该想到的是 hashMap。。。哎，虽然是在归纳双指针类型的题，但是不应该被套路套住。
方法1： hashMap
hashMap的解法比较直观易懂
hashMap (1).gif
用hashmap需要注意的是，这里要求数组里

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。

那就要记录第一个数组的每个元素的出现次数，然后在遍历第二个数组时，遇到相同的再减1。 当减到0时，即使以后第二个数组里还有相同元素，也不再添加。这样就保证了两个数组里，以少的那个为准。
另外为了效率，一开始对两个数组进行了调换，hashMap里存的是小的数组信息。

  1. var intersect = function(nums1, nums2) {
  2.   if (nums1.length > nums2.length) {
  3.     [nums1, nums2] = [nums2, nums1]
  4.   }
  5.   const arr = []
  6.     const map = new Map
  7.   for (let i = 0; i < nums1.length; i++) {
  8.     if (map.has(nums1[i])) {
  9.            map.set(nums1[i], map.get(nums1[i]) + 1)
  10.     } else {
  11.       map.set(nums1[i], 1)
  12.       }
  13.     }
  14.   for (let j = 0; j < nums2.length; j++) {
  15.       if (map.has(nums2[j]) && map.get(nums2[j]) > 0) {
  16.         arr.push(nums2[j])
  17.       map.set(nums2[j], map.get(nums2[j]) - 1)
  18.     }
  19.   }
  20.   return arr
  21. }

方法2： 双指针
这题也可以用双指针解法。
这题是要求求出两个数组的交集，只要是有相同的元素，就是交集，而不仅仅是有连续的元素才算是交集。这个要首先明确。
难点在于，如何移动两个指针呢？
比如说两个数组 [9,4,3,1] 和 [3,2,1]，它们有重叠的元素 3, 1 但是指针该怎么移动呢？如果说同时移动，肯定不行。如果第一个先移动，直到碰到相同的，再进行移动，也不行。
这里有个技巧，就是把两个数组按照从小到大的顺序排序。
然后两个数组从0开始，如果元素不相等，则把值较小的元素的指针向右移动一位。如果相等，则俩指针都移动。
因为迭代的条件是任意一个数组走完，而且谁小谁移动，就保证了 重复元素 是按照数组中的最小出现次数出现。

  1. /**
  2.  * @param {number[]} nums1
  3.  * @param {number[]} nums2
  4.  * @return {number[]}
  5.  */
  6. var intersect = function(nums1, nums2) {
  7.   let i = 0
  8.   let j = 0
  9.   nums1 = nums1.sort((a, b) => a - b)
  10.   nums2 = nums2.sort((a, b) => a - b)
  11.   const arr = []
  12.   while (i < nums1.length && j < nums2.length) { // 任意一个数组走完
  13.     if (nums1[i] === nums2[j]) {
  14.       arr.push(nums1[i])
  15.       i++
  16.       j++
  17.     } else {
  18.       if (nums1[i] < nums2[j]) {
  19.         i++
  20.       } else {
  21.         j++
  22.       }
  23.     }
  24.   }
  25.   return arr
  26. };