快慢指针

链表题目简单分为三类：

• 链表的处理：合并，删除等
• 链表的反转以及衍生
• 链表成环及其衍生

做链表处理类问题需要把握一个中心思想——即处理链表的本质，就是处理链表节点之间的指针关系。

在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分两类：左右指针和快慢指针。

左右指针，即两个指针相向或者相背而行；快慢指针，即两个指针同向而行，一块一慢。

对于单链表，大部分技巧都属于快慢指针；对于数组，我们把索引当作数组中的指针。

快慢指针技巧

原地修改

数组中常见的快慢指针技巧，比如原地修改数组

26. 删除有序数组中的重复项 | 力扣

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

高效解决这道题就要用到快慢指针技巧：

让慢指针slow走在后面，快指针fast走在前面探路，找到一个不重复的元素就赋值给slow并让slow前进一步。

这样就保证了nums[0…slow]都是无重复元素，fast遍历完整个数组后，nums[0…slow]即是整个数组去重的结果。

var removeDuplicates = function(nums) {
    if (nums.length == 0) {
        return 0;
    }
    let slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // 维护 nums[0..slow] 无重复
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // 数组长度为索引 + 1
    return slow + 1;
};

力扣第83题「删除排序链表中的重复元素」，链表去重与数组去重相似，唯一的区别是把数组赋值操作变成操作指针而已。

var deleteDuplicates = function(head) {
  if(head === null) return null
  let fast =head,slow = head
  while(fast !==null){
​    if(fast.val !== slow.val){
​      slow.next = fast
​      slow = slow.next
​    }
​    fast++
  }
  // 断开与后面重复元素的连接
  slow.next = null;
  return head;
};

(说起来，去重数组用Set()在力扣居然也能通过。)

滑动窗口

暂时不会，会了再说吧