代码随想录-双指针

27.移除元素

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    //双指针
    let slow = 0 ,fast = 0;
    //这里不减一
    for(fast = 0 ; fast < nums.length ; fast++ ){
        if(nums[fast] != val){
            nums[slow] = nums[fast]
            slow ++
        }
    }
    //为什么返回slow ？ 
    //slow储存的是不存在val的前n个值的数组下标，根据题目要求，slow后面的不需要考虑
    return slow
};

344.反转字符串

双指针完事

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
    // 双指针交换字符
    let a = -1,b = s.length
    while(++ a < --b){
        [s[a], s[b]] = [s[b], s[a]]
    }
    return s
};

剑指Offer 05.替换空格

数组填充，先找到填充后的大小，再从后往前填充（节省时间复杂度）

/**
 * @param {string} s
 * @return {string}
 */
/**
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
    为什么要从后向前填充，从前向后填充不行么？
    从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。
这么做有两个好处：
    不用申请新数组。
    从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
 */
var replaceSpace = function(s) {
   // 字符串转为数组
  const strArr = s.split("");
  let count = 0;
  // 计算空格数量
  for(let i = 0; i < strArr.length; i++) {
    if (strArr[i] === ' ') {
      count++;
    }
  }
    // 双指针一个指向原长度的尾巴，一个指向填充后长度的尾巴
  let left = strArr.length - 1;
  let right = strArr.length + count * 2 - 1;
    //遍历原字符串
    while(left > -1){
        if(strArr[left] === ' '){
            strArr[right --] = '0'
            strArr[right --] = '2'
            strArr[right --] = '%'
            left --
        }else{
            strArr[right --] = strArr[left --]
        }
    } 

  // 数组转字符串
  return strArr.join('');
};

151.翻转字符串里的单词

先按空格分割，然后双指针去除多余空格，然后直接reverse即可

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    let sArr = s.split(' ')
    // 删除多余空格：双指针
    let slow = 0,fast = 0
    while(fast < sArr.length){
        if(sArr[fast] === ''){
            fast ++
        }else{
            sArr[slow ++] = sArr[fast ++]
        }
    }
    sArr = sArr.slice(0,slow)

    sArr.reverse()
    return sArr.join(' ')
};

206.反转链表

方法一：递归

/**
 * 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 reverse = function(pre, head) {
    // 空链表直接返回
    if(!head) return pre;
    // 保存原链表的下一个元素
    const temp = head.next;
    // 反转
    head.next = pre;
    // pre往下挪一位
    pre = head
    // 递归
    return reverse(pre, temp);
}

var reverseList = function(head) {
    return reverse(null, head);
};

方法二：双指针

/**
 * 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 reverseList = function(head) {
    // 如果原链表为空或只有一个元素，直接返回
    if(!head || !head.next) {
        return head;
    }
    // temp用来保存链表元素 pre为反转之后的头节点
    // pr和ecur形成双指针
    let temp = null, pre = null, cur = head;
    while(cur) {
        temp = cur.next
        cur.next = pre
        // pre往下挪一位
        pre = cur
        // cxur往下挪一位
        cur = temp
    }
    // temp = cur = null;
    return pre;
};

19.删除链表的倒数第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) {
    // 一次扫描找到倒数第n个节点
    // 在填充一个头部之后，采取双指针法
    // 一个快指针指向第n+1个节点，一个慢指针指向头部节点
    // 当快指针挪到最后一个 ,慢指针所指的就是倒数第n个
    let ret = new ListNode(0, head)
    let slow = fast = ret
    while(n > 0){
        fast = fast.next
        n --
    }
    while(fast.next != null){
        fast = fast.next
        slow = slow.next
    }
    // 跳过下一个数 相当于删除
    slow.next = slow.next.next
    // 返回ret.next
    return ret.next
};

面试题02.07. 链表相交

简单来说，就是求两个链表交点节点的指针。 这里要注意，交点不是数值相等，而是指针相等。

方法是先通过两个链表的长度差值找到相同的起始结点,然后双指针遍历

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    // 分别求出链表A和链表B的长度,并得到他们长度的差值n
    // 如果一个比较小,然后把长的那个(比如A)往后移n
    // 现在往后移之后的A和比较短的B长度相等,使用双指针即可
    let lengthA = lengthB = 0;
    let headACopy1 = headACopy2 = headA, headBCopy1 = headBCopy2 = headB
    while(headACopy1 != null){
        lengthA ++;
        headACopy1 = headACopy1.next
    }
    while(headBCopy1 != null){
        lengthB ++;
        headBCopy1 = headBCopy1.next
    }
    // 如果A长,则要把A往后挪
    if(lengthA > lengthB){
        let n = lengthA - lengthB
        while(n --){
            headACopy2 = headACopy2.next
        }
    }
    // B更长,把B往后挪
    if(lengthB > lengthA){
        let n = lengthB - lengthA
        while(n --){
            headBCopy2 = headBCopy2.next
        }
    }
    // 以上统一了开始节点之后的长度,现在开始双指针遍历
    while(headBCopy2 != null){
        // 注意是同一个节点,不是同一个值(不能用.val代替)
        if(headACopy2 === headBCopy2){
            return headBCopy2
        }
        headACopy2 = headACopy2.next
        headBCopy2 = headBCopy2.next
    }
    return null
};

142.环形链表Ⅱ

环形指针，非常绕

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 先判断是否是环形链表
var detectCycle = function(head) {
    // 1或2个节点，直接返回
    if(!head || !head.next) 
        {
            return null;
        }
    // 双指针遍历链表
    let slow =head.next, fast = head.next.next;
    // 慢指针一次走一个，快指针一次走两个，如果有环，必定会在环里相遇
    while(fast && fast.next && fast!== slow) {
        slow = slow.next;
        fast = fast.next.next; 
    }
    // 这说明没环，直接返回 
    if(!fast || !fast.next ) {
        return null;
    }
    // 这时，结束了上面的while循环后，slow和fast节点均在环内相遇
    // 慢指针走了x + y步
    // 快指针位于环内 ，走了x + y + n(y + z)步
    // 于是2(x + y) = x + y + n(y + z) ,即 x = n(y + z) - y
    // 即x = (n - 1) (y + z) + z
    // 当 n为1的时候，公式就化解为 x = z，
    // 这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
    // 让slow重新指向头部
    slow = head;
    
    // 快慢指针分别一个一个往后挪，会同时到达环形入口
    while (fast !== slow) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};

15.三数之和

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
/**
nums.sort()
for first = 0 .. n-1
    if first == 0 or nums[first] != nums[first-1] then
        // 第三重循环对应的指针
        third = n-1
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                // 向左移动指针，直到 a+b+c 不大于 0
                while nums[first]+nums[second]+nums[third] > 0
                    third = third-1
                // 判断是否有 a+b+c==0
                check(first, second, third)

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */  

/**
怎么确定去重 ？a ， b ， c 三个数
首先这里已经升序排序了。
a 去重 ：
a 是第一次遍历，本题中是sortArr[i]，去重的时候选择sortArr[i] != sortArr[i - 1]而非sortArr[i] != sortArr[i + 1])
因为a是第一个数，应当允许其后面有值与其相等，例如{-1,-1,2}的情况。
sortArr[i] != sortArr[i + 1])会直接把{-1,-1,2}去掉。
b、c去重：同a

 */
var threeSum = function(nums) {
       let resultArr = []
       //注意 升序排序方法nums.sort(((a,b) => a-b))，不能直接nums.sort
    let sortArr = nums.sort(((a,b) => a-b))
    let length = nums.length
    for (let i = 0; i < length - 1; i++) {
        // i是基准
        // 两个相邻的数不相等的时候，才开始循环
        if(i == 0 || sortArr[i] != sortArr[i - 1]) {
            let k = length - 1
            // j和k形成双指针，j ++ ，k --
            for (let j = i + 1; j < sortArr.length - 1; j++) {
                // 这里是找到第二个数
                if(j == i + 1 || sortArr[j] != sortArr[j - 1]) {
                    // 从后往前找第三个数 
                    // 因为已经排序过来 所以当前两个数固定从后往前找第三个时，三数之和必定是从大到小
                    while(sortArr[i] + sortArr[j] + sortArr[k] > 0 && k > j + 1){
                         k --
                    }
                    //找到咯
                    if(sortArr[i] + sortArr[j] + sortArr[k] === 0 && k > j){
                      resultArr.push([sortArr[i],sortArr[j],sortArr[k]])
                    }
                }
            }
        }
    }
    return resultArr
};

18.四数之和

和三数之和一样的思路。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
   let resultArr = []
       //注意 升序排序方法nums.sort(((a,b) => a-b))，不能直接nums.sort
    let sortArr = nums.sort(((a,b) => a-b))
    let length = nums.length
    for (let i = 0; i < length - 1; i++) {
        if(i == 0 || sortArr[i] != sortArr[i - 1]) {

            for (let j = i + 1; j < sortArr.length - 1; j++) {
                if(j == i + 1 || sortArr[j] != sortArr[j - 1]) {
                    for(let k = j + 1; k < sortArr.length - 1;k ++){
                        if(k == j + 1 || sortArr[k] != sortArr[k - 1]){
                                        let z = length - 1
                            while(sortArr[i] + sortArr[j] + sortArr[k] + sortArr[z] > target && z > k + 1){
                                z --
                            }
                         //找到咯
                            if(sortArr[i] + sortArr[j] + sortArr[k] + sortArr[z] === target && z > k){
                                resultArr.push([sortArr[i],sortArr[j],sortArr[k],sortArr[z]])
                            }
                        }
                    }

                }
            }
        }
    }
    return resultArr
};