双指针

分类

• 快慢指针：解决链表问题（如判断链表是否含环）
• 左右指针：字符串或数组问题（如二分法）
• 滑动窗口
  

快慢指针

初始化时，一般快慢指针都指向链表的head.

问题1：链表是否含环？

对于一般链表而言

function hasCycle(head){
    while(head){
      head = head.next
  }
  return false
}

但是这种情况对于环形链表就会陷入死循环。

function hasCycle(head){
    let fast,slow;
  fast = slow = head;
  while(fast&&fast.next){
      fast = fast.next.next;
    slow = slow.next;
    if(fast===slow) return true;
  }
  return false;
}

使用快慢指针后，快指针每次移动两步，慢指针每次移动一步，最终快指针比慢指针快一圈，即fast===slow

问题2：已知链表中含有环，返回这个环的起始位置？

不理解
**

问题3：寻找链表的中点

function getMid(head){
    let fast,slow;
  fast = slow = head;
  while(fast&&fast.next){
      fast = fast.next.next;
    slow = slow.next
  }
  return slow;
}

当fast移动2k步的时候，slow移动k步

问题4：寻找链表的倒数第 k 个元素

思路：先让fast移动k步，然后再让fast slow以同样的速度移动，当fast到达链表尾端的时候，slow就在倒数第k个元素。

function getK(head,k){
 let fast,slow;
  fast = slow = head;
  while(k>0){
      fast = fast.next;
    k--;
  }
  while(fast){
      fast = fast.next;
    slow =slow.next;
  }
  return slow;
}

左右指针常见用法

左右指针在数组中实际是指两个索引值，一般初始化为 left = 0, right = nums.length - 1

问题1：二分法

function binarySearch(list,target){
 let left = 0,right= list.length-1;//左右均是闭区间
  while(left<=right){
      const mid = left +Math.floor((right-left)/2);
    if(list[mid]===target){
        return mid;
    }else if(list[mid]>target){
        right = mid-1;
    }else if(list[mid]<target){
      left = mid+1; 
    }
  }
  return -1;
}

问题2：两数之和

function twoSum(list,target){
    let left = 0,right = list.length-1;
  while(left<right){
      const sum = list[left]+list[right];
    if(sum===target)return [left,right]
    if(sum<target) left++;
    if(sum>target) right++;
  }
  return[-1,-1];
}

问题3：反转数组

function reverse(list){
    let left = 0,right=list.length-1;
  while(left<right){
      [list[left],list[rigth]] = [list[right],list[left]]
    left++;
    right--;
  }
  return list;
}