双指针

今天做了一个题目：Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example 1:

Given nums = [3,2,2,3], val = 3,
Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length.

大概就是把数组中与val一致的数值去掉，然后，返回与val一致的元素的个数，题目不允许额外再使用一个数组。

我上传一下我写的代码

var removeElement = function(nums, val) {
  let leave = 0
  let wipe = 0
  let flag = 0
  for( ; wipe < nums.length;  wipe++){
    if(nums[wipe] === val){
      for(leave = wipe; leave < nums.length; leave++){
          nums[leave] = nums[leave + 1]
      }
      wipe--
      flag++
    }   
  }
  return nums.length - flag
};

上传之后我看了一下排在我前面人的代码

var removeElement = function(nums, val) {
    var first = 0
        var last = nums.length - 1
        while (first < last) {
            if (nums[first] == val) {
                nums[first] = nums[last]
                last--
            } else{
                first++
            }
        }
        if (nums[first] != val) {
            first++
        }
        return first
};

双指针

他的写法时间复杂度是O(n)，而我的是O(n^2)，因为他用了双指针法(two-pointers),
双指针(这里的指针不同于c语言的指针，这里说的是数组的下标)，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。由于数组有一定的顺序，使用这种方法往往可以简化运算。

双指针的使用场景

求元素和

eag:给一个有序数组和一个数值，查找数组中是否有任意两个元素的合为指定的数值，有的话返回元素的下标(有多对数值只返回一对)。
解决的思路是，给两个游标一个指向数组首(star)，一个指向数组尾(end)。判断两个元素合(x)与数值(y)之间的关系，我们假定数组是从小到大排序的，如果 x > y 我们就给 end + 1 ,如果x < y 我们就给 star + 1。

hoare的双向扫描快速划分法()

算法原理：使用left和right将数组划分成三部分，left之前的部分为小于等于划分元素P的值，right之后的部分为大于划分元素P的值，left和right之间的部分是没有进行划分的区域。外循环使得left自左向右遍历，同时right自右向左遍历，在这个过程中当left遇见大于P的值则停止，等待right遇见小于等于P的值又停止之后，交换他们的值，这个循环在left和right相遇或者交叉之后停止。最后交换a[r]和left的值，并返回left；
参考链接

求链表中间元素

对于单链表求中间元素的问题，经典的作法是采用两个指针，初始化都指向链表表头，移动开始时，快指针移动两步，慢指针移动一步。当快指针的next为null或者快指针为null的时候，慢指针所指的就是单链表的中间元素(注意奇数个元素和偶数个元素的处理)

当然这个不是全部啦，以后发现的话再慢慢补上。