算法双指针的两种方式

双指针的两种方式

左右双指针

盛最多水的容器

let array = [1,8,6,2,5,4,8,3,7];
let maxarea = 0, L = 0, R = array.length;
while(L < R) {
	maxarea = Math.max(maxarea, Math.min(array[L], array[R]) * (L - R));
    array[L] < array[R] ? L++ : R--;
}

左右双指针的要点在于两个指针分别从数组两侧开始，左边递增、右侧递减。当左右指针相遇时，循环停止。

时间复杂度是O(n)。空间复杂度是O(1)

快慢指针

删除排序数组中的重复项

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  if(nums === null || nums.length ===0) return 0;
  let p = q = 0;
  while(q < nums.length) {
    if (nums[p] != nums[q]) {
      if (q - p > 1) {
        nums[p + 1] = nums[q];
      }
      p++;
    }
    q++;
  }
  return p + 1;
};
removeDuplicates([1,1,2]);

快慢指针的要点在于一个是慢指针、一个是快指针。快指针循环的索引，用来索引数据，慢指针充当记录员，记录某个标识。 当满足某个条件后，进行操作、同时更新慢指针的记录。

嵌套循环其实就是一个快慢双指针。