题目一览图

数组相关 - 图1

零、数组概述

数组是基本的数据结构。它存储在连续的空间中，可以由连续的整数索引。这注定了它的优势在于可以用恒定的时间访问内部的特定元素，根据公式就是 array_addr + elem_size * i 。
**

一、排序算法

类型概述

一般来说，不会考察具体的排序算法，直接使用语言自带的 sort 算法即可，但是其中的思想还是必须理解的，有的题目就是在传统排序算法中加入一些特殊的条件。

【快速排序】

  1. const quick_sort( q, l,  r)
  2. {
  3.     if (l >= r) return;
  5.     let i = l - 1, j = r + 1, x = q[l + r >> 1];
  6.     while (i < j)
  7.     {
  8.         do i ++ ; while (q[i] < x);
  9.         do j -- ; while (q[j] > x);
  10.         if (i < j) swap(q[i], q[j]);
  11.     }
  12.     quick_sort(q, l, j), quick_sort(q, j + 1, r);
  13. }

【归并排序】

const merge_sort(q,l, r)
{
    if (l >= r) return;

    const mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    let k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

二、双指针

题目概述

【双指针】题目主要解决的是数组查找问题，本质上不断移动指针的位置，最终得到符合条件的结果。类型上包含【快慢指针】、【二分查找】和【滑动窗口】。由于这三种题型套路相对独立，故在后文单独处理。（ PS：快慢指针会在【链表】中详细阐述，但是会在【原地修改】题目中有所体现。）

题目分类

分支一「基本遍历」

【基本遍历】指针只起定位作用，按照题目要求进行移动。该类型实现一般比较简单，难点在于【题目理解】和【分类讨论】上，如何按照题目写出所有处理的可能是问题的关键。

分支二「左右指针」

【左右指**针】在数组中指定两个索引值，找到符合要求的左右边界。
第一种基本题型是【边界缩小】。一般先设置左右指针指向数组的左右边界 l = 0, r = array.length 。然后根据题目的要求，不断缩小边界，直至得到符合要求的结果。注：【二分查找】属于这种。**

const fun = function(nums) {
      let i = 0 , j = nums.length - 1;
    while( i < j ){
        if( check(nums[i],nums[j]) ) return res;
        i++,j--;
    }
    return null;
};

第二种基本题型是【灵活边界】。我们需要不断维护左右边界，得到符合条件的一个范围。

分支三「原地修改」

【原地修改】就是在不使用额外数组空间的基础上，使用O(1)的额外空间，在原地修改数组的内容。本类型方法无外乎【快慢指针】和【左右指针】，只是因为该类型题目比较统一，故统一整理
第一种基本题型主要考察【快慢指针】，如 删除元素 ，比对元素。具体为快指针 fast 先走，探索符合条件的元素，如果 fast 遇到符合条件的元素，将该元素赋给慢指针 slow ，然后 slow 向前一步。当 fast 遍历完这个数组，数组[0...slow] 即为所得。一般来说，快指针 fast 从头遍历到结尾，所以可以直接用 for 循环代替，慢指针 slow 简化为变量 k 。其中条件判断抽象为 check() 函数。

const fun = function(nums, val) {
    let k = 0;
    for( let i = 0 ; i < nums.length ; i++ ){
        if( check(val) ) nums[k++] = nums[i];
    }
    return k;
};

第二种基本题型主要考察【元素交换】，也就是 swap() 函数的使用，由于本文采用的 JavaScript 不具备该函数，需要先自己实现，详见下代码（二维矩阵做相应调整）。
比较常见的操作是数组翻转，数组左移右移之类的操作，本质上采用的是【左右指针】定位元素的思想。

const swap = (nums,i,j) =>{
    const tmp = nums[i];
  nums[i] = nums[j] , num[j] = tmp;
}

题型一 | 基本遍历

题型串联

1 最后一个单词的长度

【概述】字符串遍历
【题目描述**】
给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。
如果不存在最后一个单词，请返回 0 。
【更新条件**】

  • 【分析】题目要求返回最后一个单词长度，具体分为两步清空末尾空格，然后记录非空格（单词）的长度。

  • 【指针移动过程】一共使用两个指针 p1 和 p2 ，分别定位在最后一个单词的开头结尾。

    1. 【清除空格】p1 从后向前遍历，移动至第一个非空元素，while( p1>=0 && s[p1]===' ') p1--。
    2. 【统计长度】p2 从 p1 继续从后向前遍历，移动至第一个空格，let p2 = p1 , while(p2>=0 && s[p2]!=' ') p2--。
      var lengthOfLastWord = function(s) {
let p1 = s.length - 1;
while( p1>=0 && s[p1]===' ') p1--;
if(p1<0) return 0 ;
let p2 = p1;
while(p2>=0 && s[p2]!=' ') p2--;
return p1 - p2 ;
};

      2 外观数列

      【概述】 字符串遍历
      【题目描述**】
      给定一个正整数 n ，输出外观数列的第 n 项。
      「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
      【遍历条件**】

  • 【分析】本题核心就是统计重复项，然后以【重复次数+数字】的形式输出。

  • 【指针移动过程】一共使用两个指针 p1 和 p2 。

    var countAndSay = function(n) {
let res = '1';

for( let i = 1 ; i < n ; i++ ){
   let t = '';
   for( let j = 0 ; j < res.length;){
       let k = j + 1 ;
       while( k < res.length && res[j] === res[k] ) k++;
       t += (k-j) + res[j];
       j = k;
   }
   res = t;
}
return res;
};

    3 最长公共前缀

    【概述】 字符串遍历
    【题目描述**】
    编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。
    【遍历条件**】

  • 【分析】题目要求查找字符串数组中的最长公共前缀。

    • 前缀：说明是连续元素，用指针 i 遍历每个字符串的元素。
    • 公共：说明是一样的元素，可以都和 strs[0][i] 对比。

  • 【跳出条件】

    • i 长度大于其中一个字符串长度，肯定也超出公共子串的长度，所以直接跳出。
    • str[i] 不等于 strs[0][i] ，说明不相同，所以直接跳出。
      var longestCommonPrefix = function(strs) {
if(!strs.length) return '';
let res = '';
for(let i = 0 ;  ; i++){
if( i >= strs[0].length) return res;
const c = strs[0][i];
for( let str of strs ){
    if( i > str.length || c !== str[i]) return res;
}
res += c;
}
};

      题型二 | 左右指针

      题型串联

      1 三数之和

      【概述】 左右指针
      【题目描述**】
      给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
      【遍历条件**】

  • 【分析】题目要求找到三数和为 0 的时刻，我们可以使用双指针不断缩小 0 所在的范围，即 0 存在于和从正跳到负的时候（先排序）。

  • 【需要注意的问题】

    • 【有重复数字】需要去重，当 nums[i] === nums[i-1] 时，跳过。
    • 【判断条件】 nums[i] + nums[j] + nums[k-1] >= 0 ，注意使用的是 k-1 。
      var threeSum = function(nums) {
const res = [];
nums.sort((a,b)=>a-b);
for( let i = 0 ; i < nums.length ;i++){
if( i && nums[i] === nums[i-1] ) continue;
for( let j = i + 1 , k = nums.length - 1 ; j < k ; j++ ){
    if( j > i + 1 && nums[j]===nums[j-1] ) continue;
    while( j < k - 1  && nums[i] + nums[j] + nums[k-1] >= 0 ) k--;
    if(nums[i] + nums[j] + nums[k] === 0) res.push([nums[i] ,nums[j] ,nums[k]]);
}
}
return res;
};

      2 最接近的三数之和

      【概述】 左右指针
      【题目描述**】
      给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
      【遍历条件**】

  • 【分析】题目要求找到三数和与 target 最接近的时刻，跟上题一样，我们可以使用双指针不断缩小 0 所在的范围，即 0 存在于和从正跳到负的时候（先排序），但是多了一个最小差值的判断。

  • 【需要注意的问题】。

    • 【差值判断】由于差值可以是正负，所以要判断两次最小差值。
    • 【判断条件】 nums[i] + nums[j] + nums[k-1] > 0 ，注意使用的是 k-1 。然后分别判断 k 和 k-1 时候的差值。 ```javascript var threeSumClosest = function(nums, target) { nums.sort((a,b)=>a-b);

    let sum = 0; let dif = Infinity; for(let i = 0 ; i < nums.length ; i++){ for( let j = i+ 1 , k = nums.length-1 ; j < k ; j ++ ){

       while( j < k-1 && nums[i] + nums[j] + nums[k-1] > target) k--;
   let newSum = nums[i] + nums[j] + nums[k];
   let newDif = Math.abs(newSum-target)
   dif = Math.min(dif,newDif);
   sum = dif === newDif ? newSum : sum;
   if(k-1 > j){
       newSum = nums[i] + nums[j] + nums[k-1];
       newDif = Math.abs(newSum-target)
       dif = Math.min(dif,newDif);
       sum = dif === newDif ? newSum : sum;
   }

    } } return sum; }; ```

    3 四数之和

    【概述】 左右指针
    【题目描述**】
    给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
    【遍历条件**】

  • 【分析】题目要求找到四数和为 target 的时刻，与找 0 本质无差别，可认为是 四数之和 - target = 0。然后由于是四数加和，所以要再加一层循环。

  • 【需要注意的问题】

    • 【有重复数字】需要去重，当 nums[i] === nums[i-1] 时，跳过。
    • 【判断条件】 nums[i]+nums[j]+nums[k]+nums[u-1]>=target ，注意使用的是 k-1 。
      var fourSum = function(nums, target) {
const res = [];
nums.sort((a,b)=>a-b);
for(let i = 0 ; i < nums.length ; i++){
if( i && nums[i] === nums[i-1]) continue;
for(let j = i + 1 ; j < nums.length ; j++){
    if( j > i + 1 && nums[j]===nums[j-1]) continue;
    for( let k = j + 1 , u = nums.length-1 ; k < u ; k++){
        if( k > j + 1 && nums[k]===nums[k-1]) continue;
        while( k < u-1 && nums[i]+nums[j]+nums[k]+nums[u-1]>=target) u--;
        if(nums[i]+nums[j]+nums[k]+nums[u] === target){
            res.push([nums[i],nums[j],nums[k],nums[u]]);
        }
    }
}
}
return res;
};

      4 螺旋矩阵

      【概述】 左右指针 * 2
      【题目描述**】
      给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
      【遍历条件**】

  • 【分析】题目要求按照螺旋顺序输出序列，可以用四个指针不断缩小范围实现。

    var spiralOrder = function(matrix) {
if (matrix.length === 0) return []
const m = matrix.length , n = matrix[0].length;
let top = left = 0 , bottom = m - 1  , right = n - 1;
const res = [];
while(top<bottom && left<right){
   for(let i = left ; i < right ; i++) res.push(matrix[top][i]);
   for(let i = top ; i < bottom ; i++) res.push(matrix[i][right]);
   for(let i = right ; i > left ; i--) res.push(matrix[bottom][i]);
   for(let i = bottom ; i > top; i--) res.push(matrix[i][left]);
   top++,left++,bottom--,right--;
}
if (top === bottom)
for (let i = left; i <= right; i++) res.push(matrix[top][i])
else if (left === right) 
   for (let i = top; i <= bottom; i++) res.push(matrix[i][left])
return res
};

    5 螺旋矩阵 II

    【概述】 左右指针 * 2
    【题目描述**】
    给定一个正整数 n，生成一个包含 1 到 n 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
    【遍历条件**】

  • 【分析】题目要求按照螺旋顺序输出矩阵，可以用四个指针不断缩小范围实现。

  • 【缩小过程】按照以下顺序

    • 【上边界缩小】上边界指向的 t 行完成遍历 for(let i = l; i <= r; i++) 。
    • 【右边界缩小】右边界指向的 r 行完成遍历 for(let i = t; i <= b; i++) 。
    • 【下边界缩小】下边界指向的 b 行完成遍历 for(let i = r; i <= l; i++) 。
    • 【左边界缩小】左边界指向的 l 行完成遍历 for(let i = b; i <= t; i++) 。
      var generateMatrix = function(n) {
let l = 0, r = n - 1, t = 0, b = n - 1;
let mat = new Array(n).fill(n).map(()=>new Array(n).fill(0));
let num = 1, tar = n * n;
while(num <= tar){
for(let i = l; i <= r; i++) mat[t][i] = num++;
t++;
for(let i = t; i <= b; i++) mat[i][r] = num++; 
r--;
for(let i = r; i >= l; i--) mat[b][i] = num++; 
b--;
for(let i = b; i >= t; i--) mat[i][l] = num++; 
l++;
}
return mat;
};

      6 最长回文子串

      【概述】 左右指针
      【题目描述**】
      给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
      【遍历条件**】

  • 【分析】找最长的回文子串。可以每一个节点，都想两侧遍历，找到满足条件的边界。

  • 【情况1】回文字符串长度为偶数，边界初始值 l = i , r = i+1 。

  • 【情况2】回文字符串长度为奇数，边界初始值 l = i-1 , r = i+1 。

    var longestPalindrome = function(s) {
let res = '';

for( let i = 0 ; i < s.length  ; i++){
   let l = i-1 , r = i+1 ;
   while(l>=0&&r<s.length&&s[l]===s[r]) l--,r++;
   if( res.length < r-l-1 ) res = s.substr(l+1,r-l-1);
   l = i , r = i+1;
   while(l>=0&&r<s.length&&s[l]===s[r]) l--,r++;
   if( res.length < r-l-1 ) res = s.substr(l+1,r-l-1);
}
return res;
};

    7 合并区间

    【概述】 左右指针
    【题目描述**】
    给出一个区间的集合，请合并所有重叠的区间。
    【遍历条件**】

  • 【分析】问题的关键就是怎么更新每个区间的左右边界。为了方便合并区间，我们先根据左边界排序，之后只需更新有边界即可。
  • 【判断是否重叠】当【下一个区间的左边界】是否大于【当前区间的右边界】
    • 【重叠】更新右边界，右边界择最大值 r = Math.max(r,interval[1]) 。
    • 【不重叠】输出当前区间，更新左右边界。
var merge = function(intervals) {
    if(!intervals.length) return [];
    const res = [];
    intervals.sort((a,b)=>a[0]-b[0]);
    let l = intervals[0][0] , r = intervals[0][1];
    for( let interval of intervals){
        if( interval[0] > r ){
            res.push([l,r]);
            l = interval[0] , r = interval[1];
        }else{
            r = Math.max(r,interval[1]);
        }
    }
    res.push([l,r]);
    return res;
};

8 插入区间

【概述】 左右指针
【题目描述**】
给出一个无重叠的 ，按照区间起始端点排序的区间列表。在列表中插入一个新的区间 n ，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
【遍历条件**】

  • 【分析】该问题的关键是如何更新与插入区间相关的区间。同样，为了方便后续操作，先将区间以左边界进行排序。排完序，可以将区间分为几个部分：
    • 【左部无关区间】 右边界< n[0] ，与插入区间不相关，可以直接输出。
    • 【中间纠缠区间】左边界是 n[0] ，但右边界涉及到区间合并。
    • 【右部无关区间】需要等待 n[1] 更新结束，才知道开始边界。
var insert = function(intervals, n) {
    const res = [] , len = intervals.length;
    let k = 0;
    while( k < len && n[0] > intervals[k][1] ) res.push(intervals[k++]);
    if( k < len ){
        n[0] = Math.min(intervals[k][0],n[0]);
        while( k < len && intervals[k][0] <= n[1] ) n[1] = Math.max(n[1],intervals[k++][1]);
    }
    res.push(n);
    while( k < len && intervals[k][0] > n[1] ) res.push(intervals[k++]);
    return res;
};

9 盛最多水的容器

【概述】 左右指针
【题目描述**】**
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

【题目示例**】**

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

【分析**】**

  • 本题唯一的难点是明确怎么遍历才能让面积想最大的时候靠拢？

    • 首先我们应该明确 面积 = 左边和右面的最小值 间隔 ，而且要找最大面积，左右边应该从数组两边开始。假设左边高位 x ，右边高位 y ，间隔为 t ，那么面积就是 `min(x,y)t。不妨设左边低，面积就是x*t` 。
    • 接下来的问题就是，移动谁？
      • 假设移动高边 y ，此时面积变化有两种可能：
        • y_new > x ， 此时面积没变，依旧是 min(x,y_new)*t=x*t 。
        • y_new < x ， 此时面积会变小， min(x,y_new)*t < x*t 。
        • 也就是说怎么样都不会变大。
      • 假设移动低边 x ，如果x_new > y， 面积会增大，迎来了变化的可能。

    • 所以本题的关键就是不断移动低边，不断更新左右指针，得到最大面积。

      var maxArea = function(height) {
let area = 0;
for(let i = 0, j = height.length-1; i < j ;){
   area = Math.max( area , (j-i) * Math.min(height[i],height[j]));
   if(height[i]>height[j]) j--;
   else i++
}
return area;
};

      题型三 | 原地修改

      题型串联

      1 移除元素

      【概述】原地修改 删除元素
      【题目描述**】**
      给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

    • 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

    • 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

【更新条件**】**

  • 【分析】题目要求移除所有数值等于 val 的元素，所以当数组元素不等于 val 时，慢指针进行更新。

  • 【check】** **nums[i] !== val 

    var removeElement = function(nums, val) {
let k = 0;
for( let i = 0 ; i < nums.length ; i++ ){
   if( nums[i] !== val) nums[k++] = nums[i];
}
return k;
};

    2 删除排序数组中的重复项

    【概述】原地修改 删除元素
    【题目描述**】
    给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
    不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
    【更新条件**】

  • 【分析】题目要求删除重复出现的元素，并且数组有序，所以当数组元素不等于前一个元素时，慢指针进行更新。考虑到第一个元素没有前一项，直接将 k 和 i 设置为从 1 开始即可。

  • 【check】** **nums[i] !== nums[i-1]

    var removeDuplicates = function(nums) {
let k = 1 ;
for(let i = 1 ; i < nums.length ; i++){
   if( !i || nums[i] !== nums[i-1]) nums[k++] = nums[i];
}
return k;
};

    3 移动零

    【概述】原地修改 删除元素 补齐
    【题目描述**】
    给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    【更新条件**】

  • 【分析】题目要求所有 0 移动到数组的末尾，所以我们可以先删除所有出现的 0 ，然后在补齐。

  • 【check】** **nums[i] !== 0

    var moveZeroes = function(nums) {
let k = 0;
for( let i = 0 ; i < nums.length ; i++){
   if(nums[i]) nums[k++] = nums[i];    
}
while(k < nums.length) nums[k++] = 0;
return nums;
};

    4 删除排序数组中的重复项 II

    【概述】原地修改 删除元素 限定次数
    【题目描述**】
    给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
    不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1)额外空间的条件下完成。
    【更新条件**】

  • 【分析】题目要求删除重复出现的元素，且每个元素最多出现两次。由于该数组的有序的，所以我们可以额外使用变量 c 来记录当前数字出现次数。当 nums[i] !== nums[i - 1] 说明跳到下一个数字，c 置 1 ，重新开始计数；当 nums[i] === nums[i - 1] 说明正值重复数字，计数变量 c 自增 1 ，如果自增后 c>2 ，说明到了删除时间。

  • 【check】** **nums[i] !== nums[i-1]

    var removeDuplicates = function(nums) {
let k = 1 , c = 1;
for( let i = 1 ; i < nums.length ; i++ ){
   if( nums[i] !== nums[i - 1] ) c = 1, nums[k++] = nums[i];
   else{
       c++;
       if(c<=2) nums[k++] = nums[i] ;
   }
}
return k;
};

    5 合并两个有序数组

    【概述】原地修改 合并数组
    【题目描述**】
    给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
    【合并操作**】

  • 【分析】由于两个数组都是有序数组，所以依次对比两个数组元素，并逐个放在合并数组即可。又因为题目说数组 nums1 足够大，所以直接在nums1 末端添加。

  • 【对比操作】本题设置三个指针p1 p2 p，分别指向 nums1 nums2 以及合并数组增长 nums1 ，它们的初始值分别为 m-1 ，n-1 ， m+n-1。

    • nums1[p1] >= nums2[p2]，nums1[p1] 进末尾，nums1[p--] = nums1[p1--]。
    • nums1[p1] < nums2[p2]， nums2[p2] 进末尾，nums1[p--] = nums2[p2--]。
      var merge = function(nums1, m, nums2, n) {
let p1 = m-1 , p2 = n - 1 , p = m+n-1;
while( p1>=0 && p2>=0){
if(nums1[p1] >= nums2[p2]) nums1[p--] = nums1[p1--];
else nums1[p--] = nums2[p2--];
}
for(let i = 0 ; i <= p2 ; i++ ) nums1[i] = nums2[i];
return nums1;
};

      6 反转字符串

      【概述】原地修改 元素交换 左右指针
      【题目描述**】
      编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
      不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
      【交换操作**】

  • 【分析】具体思路参考【左右指针】，就是两侧元素相互交换。

    const swap = (s,i,j)=>{
const tmp = s[i];
s[i] = s[j] , s[j] = tmp;
}
var reverseString = function(s) {
let l = 0 , r = s.length - 1;
while( l < r ){
   swap(s,l,r);
   l++,r--;
} 
};

    7 下一个排列

    【概述】原地修改 元素交换 左右指针
    【题目描述**】
    实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
    如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
    必须 原地 修改，只允许使用额外常数空间。
    【交换操作】**

  • 【分析】本题的难点在于如何寻找下一个更大的排列。

    • 首先明确排列最大的时候，数组呈递减排序，如果想转成最小排序，整体翻转即可。
    • 然后我们以 123541 为例，演示找【次大值】的过程。
      • 用变量 k 从后往前找递减排序，此时这个子数列是这几位的最大排列。如此时 k 处于 5 这个位置， 541 是递减子数列。
      • 此时结合前一位构成 3541 ，可以看出该序列是以 3 开头的最大值（因为后三位呈递减，达到最大），可以抽象为 3[max] 。 那么下一个更大值就是以 3 的次大值 4 为开头的最小值，即4[min] 。
      • 于是要做的就是先在后面的递减数列中找到次大值 4 ，并与之交换，一是换了排序的开头，二是保持了后面几位的递减特性，最后将该递减序列翻转即为小值。过程为 3541-4531-4135 。
  • 【翻转操作】本题所用的交换操作就是字符串翻转。 ```javascript const swap = (nums,a,b)=>{ const temp = nums[a]; nums[a] = nums[b] , nums[b] = temp; }

const reverse = (nums,start)=>{ let l = start , r = nums.length - 1; while( l < r ){ swap(nums,l,r); l++,r—; } }

var nextPermutation = function(nums) { let k = nums.length - 1; while( k > 0 && nums[k] <= nums[k-1]) k—; if( k === 0 ) nums.reverse(); else{ let t = k; while(t < nums.length && nums[t]>nums[k-1]) t++; swap(nums,t-1,k-1); reverse(nums,k); } };

<a name="xqzKS"></a>
#### 8 [旋转数组](https://leetcode-cn.com/problems/rotate-array/)
**【概述】原地修改 元素交换 左右指针**<br />**【题目描述****】**<br />给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。<br />**【****交换操作****】**

   - **【分析】**根据题意原数组是由 `[1 ... n]` 旋转至` [ n-k ... n , 1 ... n-k-1`]，我们发现这个过程可以转化为三次翻转，
   - **【交换过程】**
      - `[ n-k ... n , 1 ... n-k-1 ]`
      - `[ n ... n-k , n-k-1 ... 1 ]`
      - `[ 1 ... n ]` 。
```javascript
const swap = (nums,a,b)=>{
    const temp = nums[a];
    nums[a] = nums[b] , nums[b] = temp;
}

const reverse = (nums,l,r)=>{
    while( l < r ){
        swap(nums,l,r);
        l++,r--;
    }
}

var rotate = function(nums, k) {
    k %= nums.length;
    reverse(nums,0,nums.length-1);
    reverse(nums,0,k-1);
    reverse(nums,k,nums.length-1);
};

9 旋转图像

【概述】原地修改 元素交换 二维图像操作
【题目描述**】
给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
【交换操作】**

  • 【分析】题目难点在于怎么交换才能让图像顺时针旋转 90 度，具体来说就是先对角翻转，再左右交换。
  • 【对角翻转】** **matrix[i][j] 和 matrix[j][i] 交换。

  • 【左右交换】** **matrix[i][j] 和 matrix[i][n-j-1] 交换。

    var rotate = function(matrix) {
const m = matrix.length, n = matrix[0].length;
for( let i = 0 ; i < m ; i++){
   for( let j = 0 ; j < i ; j++ ){
       const tmp = matrix[i][j];
       matrix[i][j] = matrix[j][i],matrix[j][i]= tmp;
   }
}
for( let i = 0 ; i < m ; i++){
   for( let j = 0 ; j < n-j-1 ; j++){
       const tmp = matrix[i][j];
       matrix[i][j] = matrix[i][n-j-1],matrix[i][n-j-1]= tmp;
   }
}
return matrix;
};

    10 颜色分类

    【概述】原地修改 元素交换 排序
    【题目描述**】
    给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
    此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
    【交换操作】**

  • 【分析】对三种颜色的元素排序，其实就是对三种重复的数字排序。我们只需要将小的元素不停往前换就行，由于有三种元素，我们需要用两个变量来记录较大两个元素的起始位置，本篇设置为 p0 ，p1 。

  • 【交换时机】
    • nums[i] === 1 说明更大值 2 的起始位置 p1 该换地，让更小的来。
    • nums[i] === 0 说明更大值 1 的起始位置 p0 该换地，让更小的来。如果此时 p0<p1 ，说明 2 站在了 1 的前面，不用说它也该让让了。 ```javascript const swap = (nums,a,b)=>{ const tmp = nums[a]; nums[a] = nums[b],nums[b] = tmp; }

var sortColors = function(nums) { let p0 = 0 , p1 = 0; for( let i = 0 ; i<nums.length ; i++){ if( nums[i] === 1 ){ swap(nums,p1,i); p1++; }else if( nums[i] == 0){ swap(nums,p0,i); if(p0<p1) swap(nums,p1,i); p0++,p1++; } } };


<a name="Yc8dE"></a>
#### 
<a name="LaeXF"></a>
## 三、二分查找

---

<a name="qmjCO"></a>
### 类型概述
**【二分查找】**对于**有序数组**的一种 `nlogn` 时间复杂度的搜索方式，本质上属于【**左右指针**】。二分查找的模板有两种，根据我们查找的条件进行选择，为了方便说明我们把条件判断设置为函数`check()` 。<br />处了传统的查找问题，一些数学问题也可以使用<br />**<br />**类型1 - 向左查找**
```javascript
const bsearch(l, r)
{
    while (l < r)
    {
        const mid = l + r >> 1;
        if (check(mid)) r = mid; 
        else l = mid + 1;
    }
    return l;
}

类型2 - 向右查找

const bsearch(l, r)
{
    while (l < r)
    {
        const mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

题型一 | 二分查找

题型串联

**

1 二分查找

【概述】**二分查找 **模板题
【题目描述**】
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
【查找条件】判断数字是否等于目**标值
【选择模板】

  • 模板1：nums[mid]>=target 时，向右缩小。

  • 模板2：nums[mid]<=target 时，向左缩小。

    // 模板1
var search = function(nums, target) {
let l = 0 , r = nums.length -1 ;

while( l < r ){
   const mid = l + r >> 1;
   if( nums[mid] >= target ) r = mid;
   else l = mid + 1;
}
return nums[l]===target?l:-1;
};
// 模板2
var search = function(nums, target) {
let l = 0 , r = nums.length -1 ;

while( l < r ){
   const mid = l + r + 1>> 1;
   if( nums[mid] <= target ) l = mid;
   else r = mid - 1;
}
return nums[l]===target?l:-1;
};

    2 第一个错误的版本

    【概述】**二分查找
    【题目描述**】
    给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
    【查找条件】isBadVersion(x)
    **【选择模板】
    给由于已经规定大于的为 true ， 那么直接选择 模板1

    var solution = function(isBadVersion) {
/**
* @param {integer} n Total versions
* @return {integer} The first bad version
*/
return function(n) {
   let l = 1 , r = n ;
   while( l < r ){
       const mid = l + Math.floor((r - l) / 2) ;
       if(isBadVersion(mid)) r = mid;
       else l = mid + 1;
   }
   return l;
};
};

    3 搜索插入位置

    【概述】**二分查找 一侧搜索
    【题目描述**】
    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    你可以假设数组中无重复元素。
    【查找条件】**判断数字是否等于目标值
    【选择模板】**
    由于当数字不存在于数组时，需要在按顺序插入数字，这就要求我们思考两个问题

  • 【插入后数组长度增加】我们要将搜索的右边界增加一，即初始值 r = nums.length。

  • 【插入位置在次小值之后位置】我们不停比较的是 nums[mid]，最后跳出的结果应该是 nums[mid]< target 并且 l = r = mid+1 ，对应 模板1 。

    var searchInsert = function(nums, target) {
let l = 0 , r = nums.length ;
while( l < r ){
   const mid = l + r >> 1;
   if( nums[mid] >= target ) r = mid;
   else l = mid + 1;
} 
return r;
};

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

    【概述】**二分查找 两侧搜索
    【题目描述**】
    给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
    如果数组中不存在目标值 target，返回 [-1, -1]。
    【查找条件】**判断数字是否等于目标值
    【选择模板】**
    由于本题要查找多个数字的左右边界，所以要分别使用两个模板，分别从左/右方向进行缩进。

  • 【确定左边界】向左缩进，使用 模板1 。

  • 【确定右边界】向右缩进，使用 模板2 。

    var searchRange = function(nums, target) {
if(!nums.length) return [-1,-1];

let l = 0 , r = nums.length - 1;
while( l < r ){
   const mid = l + r >> 1;
   if( nums[mid] >= target ) r = mid;
   else l = mid + 1;
}
if( nums[r] !== target ) return [-1,-1];
let newL = r;
l = 0 , r = nums.length - 1;

while( l < r ){
   const mid = r + l + 1 >> 1;
   if( nums[mid] <= target) l = mid;
   else r = mid - 1;
}
return [newL,r]
};

    5 搜索旋转排序数组

    【概述】**二分查找 两次搜索
    【题目描述**】
    升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。
    请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
    【查找条件】1.**判断数字是否等于第一个值（旋转点）2. 判断数字是否等于目**标值
    【选择模板】
    由于本题要数组是部分单调的，所以我们需要先找到旋转点，然后再在单调区间寻找数值。

  • 【确定旋转点】向右缩进，使用 模板2 。

  • 【确定目标位置】都可 。

    var search = function(nums, target) {
let l = 0 , r = nums.length-1;

while( l < r ){
   const mid = (l + r + 1) >> 1;
   if(nums[mid]>=nums[0]) l = mid;
   else r = mid - 1;
}

if( target >=  nums[0] ) l = 0;
else l+=1 , r = nums.length - 1; 

while( l < r ){
   const mid = l + r >> 1;
   if(nums[mid]>=target) r = mid;
   else l = mid + 1;
} 

return nums[r]===target? r : -1;
};

    6 搜索旋转排序数组 II

    【概述】**二分查找 两次搜索
    【题目描述**】
    假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
    编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
    【查找条件】1.**判断数字是否等于第一个值（旋转点）2. 判断数字是否等于目**标值
    【选择模板】
    由于本题要数组是部分单调的，所以我们需要先找到旋转点，然后再在单调区间寻找数值。

  • 【确定旋转点】向右缩进，使用 模板2 。

  • 【确定目标位置】都可 。

    var search = function(nums, target) {
if(!nums.length) return false;
let k = nums.length - 1 ;
while( k >= 0 && nums[k]===nums[0]) k--;
if( k < 0 ) return nums[0] === target;
let l = 0 , r = k ;
while( l < r ){
   const mid = l + r + 1 >> 1;
   if( nums[mid] >= nums[0] ) l = mid;
   else r = mid - 1;
}

if( target >= nums[0] ) l = 0 ;
else l += 1 , r = k;

while( l < r ){
   const mid = l + r >> 1;
   if( nums[mid] >= target ) r = mid ;
   else l = mid + 1;
}
return nums[r] === target;
};

    7 搜索二维矩阵

    【概述】**二分查找 两次搜索
    【题目描述**】
    编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。

  • 每行的第一个整数大于前一行的最后一个整数。

【查找条件】1.**判断数字在第几行 2. **判断数字在第几列
【选择模板】

  • 【确定行】因为目标值可能不存在，同题目【搜索插入位置】，采用 模板2 。
  • 【确定列】肯定有目标值，两个方法皆可 。
    var searchMatrix = function(matrix, target) {
if(!matrix.length) return false;
const m = matrix.length , n = matrix[0].length;
let l = 0 , r = m - 1;
while(l<r){
   const mid = r + l + 1 >> 1;
   if( matrix[mid][0] <= target ) l = mid;
   else r = mid - 1;
}
const tmp = l;
l = 0 , r = n-1;
while(l<r){
   const mid = r + l + 1 >> 1;
   if( matrix[tmp][mid] >= target ) r = mid;
   else l = mid + 1;
}
return matrix[tmp][l] === target ;
};

    题型二 | 数学问题

    题型串联

1 在 x 的平方根

【概述】**二分查找 搜索数
【题目描述**】
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
【查找条件】**判断数字的平方是否等于目标值
【选择模板】**
本题采用两种模板都可以。唯一要注意的就是数字太大会导致时间过长，所以可以先预处理一下 x ，使 x = x>>1 + 1 , 即缩小一半后加一。

var mySqrt = function(x) {
    let l = 0 , r = ( x >> 1 ) + 1 ;
    while( l < r ){
        const mid = l + r + 1 >> 1;
        if( mid * mid <= x ) l = mid;
        else r = mid - 1 ;
    }
    return l;
};

四、滑动窗口

类型概述

【滑动窗口】是维护一个窗口，然后不断滑动，更新答案。大体逻辑如下：

  • 我们设置左右指针 l r ，用来标记窗口的左右界限。
const slidingWindow( nums , t ){
    const need = [] , window = [];
  for(let c of t ) need[c]++;

  let l = r = 0;
  let valid = 0;

  while( r < nums.length ){
    // 新增数据操作
    const w1 = nums[r];
    r++;
    window.push(w1);


    while( window want to shrink ){
      // 移除数据操作
      const w2 = nums[l];
        l++;
      window.remove(w2);
    }
  }
}

题型串联

1 无重复字符的最长子串

【概述】**滑动窗口
【题目描述**】
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
【题目示例**】**

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

【窗口扩大】

  • 不断右移右指针 r ，统计元素出现次数。

【窗口**缩小**】

  • 【时机】【当前元素 s[r] 】已出现在【窗口】内 。

  • 【操作】右移左指针 l ，缩小窗口。

    • 如果 s[l] 等于 s[r] ，即找到在窗口中重复的元素，将其删除，让【当前元素 s[r] 】加入窗口。

    • 如果 s[l] 不等于 s[r] ，说明遇到无辜元素，但为了维护窗口，将其删除。

      var lengthOfLongestSubstring = function(s) {
const window = new Map();
let l = r = len = 0 ;

while( r < s.length ){
   const w1 = s[r];
   r++;

   if( window.has(w1) ) window.set(w1,2);
   else window.set(w1,1);

   while( window.get(w1) === 2 ){
       const w2 = s[l];
       l++;
       if( w2 === w1 ) window.set(w1,1);
       else window.delete(w2);
   }
   len = Math.max(len,r-l);
}
return len;
};

2 最小覆盖子串

【概述】**滑动窗口
【题目描述**】
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “”
【题目示例**】**

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

【扩大】

  • 【跳出条件】右指针 r 遍历完整个字符串 s ，r < s.length 。
  • 【扩大条件】右指针指向的元素 s[r] 是待凑元素，need.has(s[r]) 。
  • 【扩大操作】
    • s[r] 在窗口内的数量加一，window.set(s[r],window.get(s[r])+1) 。
    • 窗口内的 s[r] 已经凑齐的话，有效长度 vaild 加一。
    • 右指针 r 自增。

【**缩小条件**】

  • 【跳出条件】有效长度 vaild 与 待凑元素列表长度相同，vaild === need.size 。
  • 【缩小条件】左指针指向的元素 s[l] 是待凑元素，need.has(s[l]) 。

  • 【缩小操作】

    • 窗口内的 s[l] 刚好满足凑齐要求，但现在要减少一个 ，所以有效程度 vaild 减一。
    • s[l] 在窗口内的数量减一，window.set(s[l],window.get(s[l])-1) 。

    • 左指针 l 自减。

      var minWindow = function(s, t) {
const need = new Map() , window = new Map();
let l = r = vaild = 0 ; 
let start = 0 , len = Number.MAX_SAFE_INTEGER;
for( const c of t ){ 
   if(need.has(c)) need.set(c,need.get(c)+1);
   else need.set(c,1); 
   window.set(c,0);
}

while( r < s.length ){
   if( need.has(s[r]) ){
       window.set(s[r],window.get(s[r])+1);
       if( window.get(s[r]) === need.get(s[r]) ) vaild++;
   }
   r++;
   while( vaild === need.size ){
       if( r - l < len ) start = l , len = r - l ;   
       if( need.has(s[l]) ){
           if( window.get(s[l]) === need.get(s[l]) ) vaild--;
           window.set(s[l],window.get(s[l])-1);
       }
       l++;
   }        
}
return len === Number.MAX_SAFE_INTEGER? "" : s.substr(start,len);
};

      3 串联所有单词的子串

      【概述】**滑动窗口
      【题目描述**】
      给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
      注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
      【题目示例**】**

      输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

      【分析】本题给出的单词长度一致，所以我们可以把单词长度看成单位。根据起始位置不同，有单词长度种划分方式。比如单词长度唯一，划分类型就有【起始索引为 0 】【起始索引为 1 】【起始索引为 2 】三种。
      【参数】

  • 设置映射 need 存储带凑的字符串集。

  • 设置变量 wordLen 为每个单词长度 。
  • 设置变量 i 为每种分类的起始索引。

【窗口扩大】

  • 不断右移右指针 r （间隔为 wordLen ），获取子串 w1=s.substr(r,wordLen) 。
  • 统计子串 w1 出现次数，如果是 need 中存在且还未凑完的字符串，有效长度 vaild 加一。
  • 如果有效长度 vaild 等于单词集合 words 的长度，说明有效，将左指针 l 存入结果。

【窗口**缩小**】

  • 【时机】右指针 r 已经超出单词集合 words 的字符长度，r >= i + n * wordLen。

  • 【操作】右移左指针 l （间隔为 wordLen ）窗口右移。

    • 获取即将移除子串 w2=s.substr(l,wordLen) 。

    • 如果w2 在 need 中，则有效长度 vaild 减一。

      var findSubstring = function(s, words) {
let res = [];
if(!words.length) return res;
const m = s.length , n = words.length , wordLen = words[0].length;

const need = new Map();

for(let word of words) need[word] = need[word] === undefined ? 1 : need[word]+1;

for(let i = 0 ; i < wordLen ; i++){
   const window = new Map();
   let vaild = 0;
   let l = r = i ;
   while( r < m  ){
       const w1 = s.substr(r,wordLen);
       r += wordLen ;
       window[w1]= window[w1] === undefined ? 1 : window[w1] + 1;
       if(need[w1] && window[w1]<=need[w1]) vaild++;
       if(vaild===n) res.push( l );

       if( r >= i + n * wordLen ){
           const w2 = s.substr( l , wordLen );
           l += wordLen ;
           window[w2]--;
           if( need[w2] && window[w2] < need[w2]) vaild--;
       }
   }
}
return res;
};