双指针

https://mp.weixin.qq.com/s/Z-oYzx9O1pjiym6HtKqGIQ
在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧。

快慢指针

原地修改数组

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

83.删除排序链表中的重复元素

其实和数组去重是一模一样的，唯一的区别是把数组赋值操作变成操作指针而已

27.移除元素

快慢指针
或者左右指针（会打乱顺序）

283.移动零

与上题类似

75. 颜色分类

189. 轮转数组

31. 下一个排列

202. 快乐数

推算得到所有数最后都会进入循环，所以可以使用快慢指针。

  1. /**
  2.  * @param {number} n
  3.  * @return {boolean}
  4.  */
  5. var isHappy = function(n) {
  6.      function getSquareSum(n){
  7.         let sum=0;
  8.         while(n>0){
  9.           sum+=(n%10)*(n%10);
  10.           n=parseInt(n/10);
  11.         }
  12.         return sum;
  13.      }
  15.      let slow=n,fast=n;
  16.      do{   //使用do while
  17.         slow=getSquareSum(slow);
  18.         fast=getSquareSum(fast);
  19.         fast=getSquareSum(fast);
  20.      }while(slow!==fast)
  21.      return slow===1;
  22. };

滑动窗口算法

https://mp.weixin.qq.com/s/ioKXTMZufDECBUwRRp3zaA
数组中另一大类快慢指针的题目就是「滑动窗口算法」。
left指针在后，right指针在前，两个指针中间的部分就是「窗口」，算法通过扩大和缩小「窗口」来解决某些问题。

  1. //滑动窗口算法算法框架 时间复杂度O(N)
  2. int left = 0, right = 0;
  4. while (right < s.size()) {
  5.     // 增大窗口
  6.     window.add(s[right]);
  7.     right++;
  9.     while (window needs shrink) {
  10.         // 缩小窗口
  11.         window.remove(s[left]);
  12.         left++;
  13.     }
  14. }


76.最小覆盖子串

找到字符串中所有字母异位词

3. 无重复字符的最长子串

  1. var lengthOfLongestSubstring = function(s) {
  2.   let result=0;
  3.   let left=0,right=0;
  4.   let world="";
  5.   while(right<s.length){
  6.     const rightStr=s[right]
  7.     right++;
  8.     let index=world.indexOf(rightStr)
  9.     if(index>-1){
  10.         left=left+index+1;
  11.     }
  12.     const length=right-left;
  13.     result=length>result?length:result;
  14.     world=s.substring(left,right);
  15.   }
  16.   return result
  17. };

左右指针

只要数组有序，就应该想到双指针技巧。

二分查找
167.两数之和 II 可以使用map吗？
翻转数组
回文串判断

977. 有序数组的平方

  1. var sortedSquares = function(nums) {
  2.   const length=nums.length
  3.   let left=0,right=length-1;
  4.   let result=Array(length);
  5.   let resIndex=length-1;
  6.   while(left<=right){
  7.      const leftNum=nums[left],rightNum=nums[right]
  8.      if(Math.abs(leftNum)<=Math.abs(rightNum)){
  9.         result[resIndex--]=rightNum*rightNum
  10.         right--;
  11.      }else{
  12.         result[resIndex--]=leftNum*leftNum
  13.         left++;
  14.      }
  15.   }
  16.   return result;
  17. };

5.最长回文子串

  1. var longestPalindrome = function (s) {
  2.   let result = '';
  3.   // 寻找以 s[l] 和 s[r] 为中心的最长回文串
  4.   function getPalindrome(s, l, r) {
  5.     while (l >= 0 && r < s.length && s[l] === s[r]) {
  6.       l--;
  7.       r++;
  8.     }
  9.     return s.substring(l + 1, r);
  10.   }
  11.   for (let i = 0; i < s.length; i++) {
  12.     //找到以 s[i] 为中心的回文串想，奇数回文串
  13.     const r1 = getPalindrome(s, i, i);
  14.     //找到以 s[i] 和 s[i+1] 为中心的回文串，偶数回文串
  15.     const r2 = getPalindrome(s, i, i + 1);
  16.     result =r1.length > result.length ? r1 :result;
  17.     result =r2.length > result.length ? r2 :result;
  18.   }
  19.   return result;
  20. };

合并两个有序数组

  1. var merge = function(nums1, m, nums2, n) {
  2.   let left=m-1,right=n-1,res=m+n-1;
  3.   if(n=0) return;
  4.   while(left>=0 || right>=0){
  5.       if(left <0 || nums1[left]<=nums2[right] ){
  6.         nums1[res]=nums2[right]
  7.         right--;
  8.         res--;
  9.       }else{
  10.         nums1[res]=nums1[left]
  11.         left--;
  12.         res--;
  13.       }
  14.   }
  15. };

二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
看到有序数组查找某一个值，则应立马想到二分查找

704. 二分查找

  1. var search = function(nums, target) {
  2.    let min=0,max=nums.length-1,mid;
  3.    while(min<=max){
  4.      mid=Math.ceil((min+max)/2);
  5.      if(nums[mid]>target){
  6.          max=mid-1
  7.      }else if(nums[mid]<target){
  8.          min=mid+1
  9.      }else{
  10.          return mid
  11.      }
  12.    }
  13.    return -1;
  14. };

69. x 的平方根

  1. var mySqrt = function(x) {
  2.     if(x<2) return x;
  3.     let left=0,right=x;
  4.     while(left<=right){
  5.       let mid=Math.floor((left+right)/2)
  6.           if((mid+1)*(mid+1)>x){
  7.               return mid
  8.           }else{
  9.               left= mid+1;
  10.           }
  11.       }else{
  12.           right = mid-1;
  13.       }
  14.     }
  15. };

34. 在排序数组中查找元素的第一个和最后一个位置

  1. var searchRange = function(nums, target) {
  2.   let min=0,max=nums.length-1;
  3.   while(min<=max){
  4.     let mid=Math.ceil((min+max)/2);
  5.     if(nums[mid]>target){
  6.         max=mid-1;
  7.     }else if(nums[mid]<target){
  8.         min=mid+1
  9.     }else{
  10.         //试探周围元素是否相等；
  11.         let left=mid,right=mid;
  12.         while(left-1>=0 && nums[left-1]===nums[mid]){
  13.             left--
  14.         }
  15.         while(right+1<nums.length && nums[right+1]===nums[mid]){
  16.             right++
  17.         }
  18.         return [left,right];
  19.     }
  20.   }
  21.   return [-1,-1];
  22. };

33. 搜索旋转排序数组

对于有序数组，可以使用二分查找的方法查找元素。
但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的。将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。 此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环.。

  1. var search = function(nums, target) {
  2.     if(nums.length<1) return -1
  3.     if(nums.length==1) return target===nums[0] ?0:-1;
  4.     let left=0,right=nums.length-1;
  5.     while(left<=right){
  6.         let mid=Math.floor((left+right)/2);
  7.         if(target===nums[mid]){
  8.             return mid;
  9.         }
  10.         if(nums[left]<=nums[mid]){
  11.             if(target>=nums[left] && target<nums[mid]){
  12.                 right = mid-1;
  13.             }else{
  14.                 left = mid+1;
  15.             }
  16.         }else{
  17.             if(target>nums[mid] && target <=nums[right]){
  18.                 left = mid+1;
  19.             }else{
  20.                 right = mid-1;
  21.             }
  22.         }
  23.     }
  24.     return -1;
  25. };

539. 最小时间差

  1. function getMinute(str){
  2.     //转成分钟
  3.     return Number(str.substr(0,1))*60*10 + Number(str.substr(1,1))*60 + Number(str.substr(3,1))*10+ Number(str.substr(4,1))
  4. }
  5. var findMinDifference = function(timePoints) {
  6.     let newTimePoiont=timePoints.sort(); //排序
  7.     let fisrtTime=getMinute(newTimePoiont[0]);
  8.     let preTime=fisrtTime,nextTime;
  9.     let res=Infinity
  10.     for(let i =1;i<newTimePoiont.length;i++){
  11.         nextTime=getMinute(newTimePoiont[i]);
  12.         res=Math.min(nextTime-preTime,res)
  13.         preTime=nextTime
  14.     }
  15.     //排序好后计算收尾，因为头一定比尾小，相减时需要考虑 5:00 20:00的情况，时间差应为9而不是15
  16.     res=Math.min(res,fisrtTime+24*60-nextTime); 
  17.     return res;
  18. };

前后缀乘积

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

  1. function getNewList(list){
  2.   const length=list.length;
  3.   let left=Array(length); //计算所有前缀和后缀元素的乘积
  4.   let right=Array(length);
  5.   let ans=Array(length);
  6.   left[0]=1;
  7.   right[length-1]=1;
  8.   for(leti=1;i<length;i++){
  9.      left[i]=list[i-1] * left[i-1]
  10.   }
  11.   for(leti=length-2;i>=0;i--){
  12.     right[i]=list[i+1] * right[i+1]
  13.     ans[i]=left[i]*right[i];
  14.   }
  15.   ans[length-1]=left[length-1]*right[length-1];
  16.   return ans;
  17. }

单调栈

单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。
时间复杂度为O（N）
数组 - 图1

496. 下一个更大元素 I

739. 每日温度

存放元素索引

503. 下一个更大元素 II

如何处理环形数组

接雨水

  1. //木桶效应，需要看短板，得到当前左边和右边的最高，取短板-当前高度
  2. //前后缀 动态规划 时间O(N),空间O(N)
  3. var trap = function(height) {
  4.    const length=height.length;
  5.    let left=Array(length),right=Array(length);
  6.    let result=0;
  7.    left[0]=height[0];
  8.    for(let i=1;i<length;i++){
  9.       left[i]=Math.max(height[i],left[i-1])
  10.    }
  11.    right[length-1]=height[length-1];
  12.     for(let i=length-2;i>=0;i--){
  13.       right[i]=Math.max(height[i],right[i+1])
  14.    }
  15.     for(let i=0;i<length;i++){
  16.       result+=Math.min(left[i],right[i])-height[i]
  17.    }
  18.    return result;
  19. };

空间复杂度还需要优化，将备忘录数组优化为双指针变量，此时空间复杂度为O（N）。

  1. /**
  2.  * @param {number[]} height
  3.  * @return {number}
  4.  */
  5. var trap = function(height) {
  6.    const length=height.length;
  7.    let result=0;
  8.    let left=0,right=length-1;
  9.    let leftMax=height[left],rightMax=height[right];
  10.    while(left<=right){
  11.        if(leftMax<=rightMax){
  12.            result+=leftMax-height[left]
  13.            left++;
  14.            leftMax=Math.max(height[left],leftMax)
  15.        }else{
  16.            result+=rightMax-height[right]
  17.            right--;
  18.            rightMax=Math.max(height[right],rightMax)
  19.        }
  20.    }
  21.    return result;
  22. };

二维矩阵

48. 旋转图像

  1. var rotate = function (matrix) {
  2.     const n = matrix.length;
  3.     for (let i = 0; i < Math.floor((n + 1) / 2); ++i) {
  4.         for (let j = 0; j < Math.floor(n / 2); ++j) {
  5.             const temp = matrix[i][j];
  6.             matrix[i][j] = matrix[n - j - 1][i];
  7.             matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
  8.             matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
  9.             matrix[j][n - i - 1] = temp;
  10.         }
  11.     }
  12. };

54. 螺旋矩阵

  1. var spiralOrder = function (matrix) {
  2.     let left = 0, right = n - 1, top = 0, bottom = n - 1, k = 1;
  3.     let result = []
  4.     while (k <= n * n) {
  5.         for (let i = left; i <= right; i++) {
  6.             result.push(matrix[top][i])
  7.         }
  8.         top++;
  9.         for (let i = top; i <= bottom; i++) {
  10.             result.push(matrix[i][right])
  11.         }
  12.         right--;
  13.         for (let i = right; i >= left; i--) {
  14.             result.push(matrix[bottom][i])
  15.         }
  16.         bottom--;
  17.         for (let i = bottom; i >= top; i--) {
  18.             result.push(matrix[i][left])
  19.         }
  20.         left++;
  21.     }
  22.     return result;
  23. };

59. 螺旋矩阵 II

  1. var generateMatrix = function (n) {
  2.     let left = 0, right = n - 1, top = 0, bottom = n - 1, k = 1;
  3.     let result = Array.from(Array(n), () => Array(n));
  4.     while (k <= n * n) {
  5.         for (let i = left; i <= right; i++) {
  6.             result[top][i] = k++;
  7.         }
  8.         top++;
  9.         for (let i = top; i <= bottom; i++) {
  10.             result[i][right] = k++;
  11.         }
  12.         right--;
  13.         for (let i = right; i >= left; i--) {
  14.             result[bottom][i] = k++;
  15.         }
  16.         bottom--;
  17.         for (let i = bottom; i >= top; i--) {
  18.             result[i][left] = k++;
  19.         }
  20.         left++;
  21.     }
  22.     return result;
  23. };

74. 搜索二维矩阵

  1. //方法一：
  2. var searchMatrix = function (matrix, target) {
  3.     //左下角的数一定比右上角大。故从左下角开始遍历，小了往上，大了往右。
  4.     let i = matrix.length - 1, j = 0;
  5.     while (i >= 0 && j < matrix[0].length) {
  6.         const num = matrix[i][j]
  7.         if (num === target) return true;
  8.         else if (num > target) i--;
  9.         else j++;
  10.     }
  11.     return false;
  12. };
  14. //方法二 二分搜索
  15. //时间复杂度：O(logmn)，其中 mm 和 nn 分别是矩阵的行数和列数。
  16. //空间复杂度：O(1)。
  17. var searchMatrix = function (matrix, target) {
  18.     const m = matrix.length, n = matrix[0].length;
  19.     let low = 0, high = m * n - 1;
  20.     while (low <= high) {
  21.         const mid = Math.floor((high + low) / 2);
  22.         const x = matrix[Math.floor(mid / n)][mid % n];
  23.         if (x < target) {
  24.             low = mid + 1;
  25.         } else if (x > target) {
  26.             high = mid - 1;
  27.         } else {
  28.             return true;
  29.         }
  30.     }
  31.     return false;
  32. };