愤怒，本质上对自己无能的宣泄

前言

大家好，我是柒八九。这篇文章是我们算法探险系列的第三篇文章。是针对数据结构方面的第二篇。上一篇JS算法探险之整数中我们介绍了关于JS整数的一些基础知识和相关算法题。我们做一个简单的前情回顾。

例如

• JS整数都以小数存储(IEEE 754格式)
• 查看一个正整数的二进制格式 (number).toString(2)
• i>>1来计算i/2,而且还是下取整

5. 用 i&1来计算 i%2
6. 还处理了很多典型的算法题

• 整数除法
• 二进制加法 ==> N 进制加法
• 前 n 个数字二进制中 1 的个数
• 只出现一次的数字

而今天，我们继续介绍一类，很基础但是无论在数据结构方向还是算法解题中都占有很大比重的数据结构 ---数组。

闲话少叙，那就开始咯。

时间不早了，干点正事哇。(郭德纲语言包)

还是老样子，附赠一首打油诗：

• 数组算法千千万，sum套路就那般
• 类型不同路不同，正整数双指针，其余尝试用S_i
• 正整数分两类，同向/反向 双指针

1. 数据有序反向针，left为首right为尾(求两数之和)

• sumVStarget, sum小，left++；sum大，right--

2. 子数组同向针，区域之和或乘积

• 先处理right,根据条件移动left
• sum/mult < target: 右移 (right++)
• sum/mult > target: 右移 (left++)
• 指针left永远不会走到指针right的右边 (left<=right)

• 非正整数用S_i(前i个数据和)

3. S_j-S_i-1 为所求
4. 找次数、长度Map(sum,count/index)来辅助

奇怪的知识点：

1. 数组的本质是对象且为异质对象

2. JS 只支持一维数组，并不支持矩阵

文章概要

1. 双指针
2. 累加数组数字求子数组之和

知识点简讲

JS数组的本质

JS数组本质上是对象

根据 EMMAScript规范，在JS中有两种对象

1. {常规对象|Ordinary Object}

2. {异质对象|Exotic Object}

这两种对象包含了JS世界中所有的对象，任何不属于常规对象的对象都是异质对象。

而数组就是异质对象，即

数组的本质是对象且为异质对象

JS 只支持一维数组，并不支持矩阵(多维数组)

在JS中，我们可以通过很多方式来构建一维数组。

let array = Array('柒','八'，'九'); // new Array / []等
复制代码

而构建多维数组，就需要借助函数来构建。

const matrix= (x,y) => 
    new Array(x).fill(0)
    .map(
      ()=>new Array(y).fill(0)
    )
复制代码

通过matrix我们构建了一个，x行，y列 且数组中值都为0的二维数组(矩阵)。

当然，我们可以在函数内部执行其他的初始化条件。然后生成满足条件的二维数组。

多维数组的话，可以套用上面的代码。

const matrixN = (i,j,z) => 
    new Array(i).fill(0)
    .map(
        ()=>new Array(j).fill(0)
        .map(
            ()=>new Array(z).fill(0)
        )
    )
复制代码

用类似的方式，我们构建了一个i（行）、j（列）及 z（深度）的矩阵。

1. 双指针

双指针是一种常见的解题思路，使用两个相反方向或者相同方向的指针扫描数组从而达到解题目的。

有两种解题思路: 反向双指针/同向双指针

1. 方向相反的双指针用来求排序数组（升序）中的两个数字之和。一个指针P1(left)指向数组的第一个数字，另一个指针P2(right)指向数组的最后一个数字，然后比较两个指针指向的数字之和（sum）与一个目标值（target）直接的大小关系。

1. sum < target: 右移 left (left++)
2. sum > target: 左移 right (right--)

2. left/right的移动方向是相反的
3. 方向相同的双指针用来求正数数组中子数组的和(sum)或者乘积（mult）。初始化的时候两个指针left/right都指向数组的第一个数字。如果两个指针之间的子数组的sum或者mult与target之间关系如下：

1. sum/mult < target: 右移 right（right++）,在子数组右边增加新的数字
2. sum/mult > target: 右移left(left++)，删除子数组最左边的数字

4. left/right的移动方向是相同的

1. 排序数组中的两个数字之和

题目描述：

输入一个递增排序的数组和一个值target,在数组中找出两个和为target的数字并返回它们的下标

提示：

数组中有且只有一对符合要求

同时一个数字不能使用两次

示例：输入数组： [1,2,4,6,10],k的值为8 输出[1,3]

分析

1. 看题干，首先一个很关键的点，就是数组已经有序，然后可以采用双指针解法的第一套：反向双指针
2. 按照既定套路， left指向首元素，right指向尾元素
3. 根据 sum VS target 移动对应的指针

代码实现

function twoSum4SortedArray(nums,target){
  let left=0,right= nums.length-1; // 初始化指针left,right 
  while(left<right && nums[left] + nums[right] != target){
    if(nums[left] + nums[right]<target){
      left++;
    }else{
      right--;
    }
  }
  return [left,right]
}
复制代码

注意：如果大家在刷leetcode等算法网站中，肯定会见过关于数组的两数之和的题。但是，这里的题干和常规的两数之和还有点区别。首先，该题干中，天生有序，所以，可以套用反向双指针的套路。

为了做区分，我们将twoSum的解题代码也直接写出来。它的解题思路是，利用了Map对数据和下标做了转换。

function twoSum(nums,target){
    let map = new Map(); // 用于，存储[nums[i],i]之间的关系
    for(let i =0;i<nums.length;i++){
        let expectValue = target - nums[i];
        // 先从map中找，是否存在指定值
        if(map.has(expectValue)){
            // 如果有，直接返回与值相对于的下标
            return [map.get(expectValue),i]
        }
        // 存储[nums[i],i]之间的关系
        map.set(nums[i],i);
    }
    return null;
}
复制代码

2. 数组中和为target的3个数字

题目描述：

输入一个数组，找出数组中所有和为target的3个数字的三元组

提示：

返回值不得包含重复的三元组

示例：输入数组： [-1,0,1,2,-1,-4],target的值为0 输出[[-1,0,1],[-1,-1,2]]

分析

1. 如果输入的数组是有序，那就可以先固定一个数，然后在该数后面的数组段中，采用双指针解法的第一套：反向双指针

• 按照既定套路， left指向固定元素的后一个元素，right指向尾元素
• 根据 sum VS target 移动对应的指针
• 该解题思路，其实就是求排序数组中的两个数字之和的升级版

2. 剔除重复三元组的时机，

• 应该是在找到符合要求(三数之和=target)时，在移动指针时，需要跳过所有相同的值

3. 针对整数数组(有正，有负)升序排序 利用sort但是需要指定排序函数

• nums.sort((a,b)=>a-b)

代码实现

function threeSum(nums,target){
  let result = [];
  if(nums.length<3) return [];
  // 人工对数据进行排序处理
  nums.sort((a,b)=>a-b);
  let i =0;
  while(i<nums.length-2){
    twoSum(nums,i,target,result);
    let temp = nums[i];
    // 剔除，重复元祖中第一个数值
    while(i<nums.length && nums[i]==temp) i++;
  }
  return result;
}
复制代码

我们把排序数组中的两个数字之和的算法，做了一个改造，因为left不在从0开始，所有需要将left的前一个位置i传入，right的逻辑不变，还是数组尾部

• left = i + 1
• right = nums.length - 1

function twoSum(nums,i,target,result){
  // 初始化指针left,right 
  let left = i + 1, right = nums.length -1;
  while(left<right){
    // 求和
    let sum = nums[i] + nums[left] + nums[right];
    // 指针移动过程 (if/else)
    if(sum === target){
      result.push([nums[i],num[left],nums[right]]);
      let temp = nums[left];
      // 剔除，重复元祖第二个数值
      while(nums[left] === temp && left < right) left++;
    }else if(sum < 0) {
      left++;
    }else{
      right--;
    }
  }
}
复制代码

我们来对比下，两个twoSum的共同和不同点。

它们的核心框架是相似的。都是利用方向双指针进行sum与target之间的数据对比。

3. 和大于或等于k的最短子数组

题目描述：

输入一个正整数组成的数组和一个正整数target,找出数组中和大于或等于target的连续子数组的最短长度

提示：

如果不存在满足条件的子数组，返回0

示例：输入数组： [5,1,4,3],target的值为7 输出2 (和大于或等于7的最短连续子数组是[4,3])

分析

1. 题干出现正整数数组/连续子数组之和， 很满足之前介绍的同向双指针解题思路
2. 一个子数组可以用两个指针表示

• left指向子数组的第一个数字
• right指向子数组的最后一个数字
• 子数组就是left/right两指针之间的所有数字的组成

3. 指针left永远不会走到指针right的右边
4. left/right初始化的时候都指向数组的第一个元素，套用上面的公式

1. sum < target: 右移 right（right++）,在子数组右边增加新的数字，子数组长度+1
2. sum >= target: 右移left(left++)，删除子数组最左边的数字，子数组长度-1

5. 题目要求，最短长度。而提供的数组为正整数，也就是说，在找到sum>=target时，为了求最短子数组，我们需要移动left进行子数组的瘦身处理 (left++)

代码实现

function minSubArrayLen(nums,target){
  let left=0,right=0; // 同向双指针，默认值
  let sum=0; 
  // 最小的长度
  let minLength = Number.MAX_SAFE_INTEGER;
  for(right=0;right<nums.length;right++){
    sum+=nums[right];
    while(left<=right && sum>=target){
      // 更新最小长度
      minLength = Math.min(minLength,right - left + 1);
      // 子数组**瘦身**处理
      sum-= nums[left++]
    }
  }
  return minLength == Number.MAX_SAFE_INTEGER?0:minLength;
}
复制代码

有几点需要唠叨一下：

• 针对一些常规的最值的初始值，一般都是反着来。例如：最小值，一般赋合理范围的最大值(Number.MAX_SAFE_INTEGER) 如果已知最大范围，我们也可以给一个定值。例如，100/1000等；那最大值，就是用0等替换
• 同向双指针 ：right先动,left视情况而动

4. 和大于或等于k的最短子数组

题目描述：

输入一个正整数组成的数组和一个正整数target,找出数组中乘积小于target的连续子数组的所有组合的个数

示例：输入数组： [10,5,2,6],target的值为100 输出 8 （[10],[5],[2],[6],[10,5],[5,2],[2,6],[5,2,6]）

分析

1. 题干出现正整数数组/连续子数组乘积， 很满足之前介绍的同向双指针解题思路，两个指针之间的数字组成一个子数组。
2. 指针left永远不会走到指针right的右边 (left<=right)
3. 两个指针初始化都指向数组的第一个数字
4. 指针移动逻辑

1. mult < target: 右移 right（right++）,在子数组右边增加新的数字，子数组长度+1 (mult变大)
2. mult >= target: 右移left(left++)，删除子数组最左边的数字，子数组长度-1(mult变小)

5. 一旦向右移动指针left到某个位置时子数组的乘积小于target,就不需要移动left。只要right保持不动，[left,right]区间的所有的子数组的乘积都一定小于target。 也就说说，两个指针之间有多少个数字，就有多少个满足条件的子数组

代码实现

function numSubarrayMultLessThanTarget(nums,target){
  let mult = 1; 
  let left =0,right=0; // 初始化指针
  let count = 0;
  for(right=0;right<nums.length;right++){
    mult *=nums[right];
    // 指针left永远不会走到指针right的右边
    while(left<=right && mult >= target){
      mult /=nums[left++];
    }
    count += right>=left?right - left +1 :0;
  }
  return count;
}
复制代码

虽然，在求正整数数组和或者乘积之间，有些具体逻辑不大相同，但是总体的思路都是利用同向双指针对数据进行处理。

2. 累加数组数字求子数组之和 （S_i）

使用双指针解决子数组之和有一个前提条件：数组中的所有数字都是正数。所有，双指针的在解决非正数的数组时，是不满足条件的。

针对非正数的数组，我们换一个思路来求子数组之和。

假设整个数组的长度为n,它的某个子数组的第一个数字的下标是i;最后一个数字的下标是j。我们做一个预处理，计算从数组下标为0的数字开始到以每个数字为结尾的子数组之和。预处理只需要从头到尾扫描一次，就能求出从下标0开始到下标0结束的子数组之和 S₀ ,以此类推，S₁,S₂,S_n-1因此，从下标为i开始到下标为j结束的子数组的和就是 S_j-S_i-1

例如：在数组[1,2,3,4,5]中，从S₂的子数组[1,2,3]之和是6，S₄的子数组[1,2,3,4,5]之和是15，那么从下标3开始到下标4结束的子数组之和[4,5]之和是9，也就是 S₄ - S₂ 即： 15 - 9 = 6

具体的思路如上，做事讲究，师出有名，既然思想有了，那就需要见真章的时候了。

1. 和为target的子数组

题目描述：

输入一个整数组成的数组和一个整数target,找出数组中数字之和等于target的连续子数组的个数

示例：输入数组： [1,1,1],target的值为2 输出 2

分析

1. 求连续子数组之和，但是数组不是正整数，所以同向双指针作废
2. 双指针作废，那我们就采用前i个数字之和的处理方式

• 从头到尾扫描数组时，求前i个数字之和，并将和保存下来
• 将数组的前i个数字之和记为x
• 如果存在一个j (j) 即，j在x前面，且数组的前j个数字之和为x-target（很重要）
• 那么数组中从第j+1个数字开始到第i个数字结束的子数组之和为target

3. 此题中需要计算和为target的子数组的个数。当扫描到数组第i个数字并求得前i个数字之和是x时，需要知道在i之前存在多少个j并且前j个数字之和等于x-target

• 所以，对于每个i,不但要保存前i个数字之和，还要保存每个和出现的次数
• 所以，我们用一个Map（哈希表）的键(key)保存前i个数字之和，值(value)保存每个和出现的次数

代码实现

function subarraySum(nums,target){
  // 构建哈希表，并初始化[0,1]
  let sumToCount = new Map();
  sumToCount.set(0,1);
  let sum = 0;
  let count =0;
  for(let num of nums){
    sum += num;
    // 统计 在当前数值下的 x-target的值
    count += sumToCount.get(sum - target) // 前面已经存在
             || 0; // 首次出现
    sumToCount.set(
        sum,
        (sumToCount.get(sum)||0)+1
      )
  }
  return count;
}
复制代码

2. 0和1个数相同的子数组

题目描述：

输入一个只包含0和1的数组，求0和1的个数相同的最长连续子数组的长度




示例：输入数组： [0,1,0] 输出 2 （两个子数组分别是[0,1]和[1,0]）

分析

1. 如果把数组中所有的0换成-1,做一个转化处理，求0/1个数相同的子数组，就变成了，求子数组之和为0。那就变成和为target的子数组的进阶版，只不过，需要求子数组中长度最长的子数组的长度
2. 那就还是采用和为target的子数组的解题思路：前i个数字之和
3. 扫描数组时累加扫描过的数字之和，如果数组中前i个数字之和为m,前j个数字(j)之和也为m,那么从j+1到第i个数字的子数组之和为0，长度为i - j
4. 利用一个Map来存储对应的下标，键(key)是从第一个数字开始累加到当前扫描到的数字之和，而值(value)是当前扫描的数字的下标


代码实现


function findMaxLength(nums){
  let sumToIndex = new Map();
  sumtoIndex.set(0,-1);
  let sum = 0;
  let maxLength =0;
  for(let i=0;i<nums.length;i++){
    // 数据转化
    sum+=nums[i]==0?-1:1;
    if(sumToIndex.has(sum)){
      maxLength = Math.max(maxLength,i-sumToIndex.get(sum));
    }else{
      // 存储关系
      sumToIndex.set(sum,i)
    }
  }
  return maxLength;
}
复制代码

我们可以看到，在和为target的子数组和0和1个数相同的子数组中，虽然有些细节是不一样的，但是总体框架还是一致的。

• 前i个数字之和 求出sum
• 利用Map 来存储sum与对应所求的(count/index)直接的关系
• 满足条件更新结果

3. 左右两边子数组的和相等

题目描述：

输入一个整数数组，如果一个数字左边的子数组的数字之和等于右边子数组的数字之和，返回该数字的下标




示例：输入数组： [1,7,3,6,2,9] 输出 3 （对应的值为6） ，下标为3的数字(值为6)的左边3个数1,7,3的和与右边两个数字2,9的和相等

分析


1. 当扫描到第i个数字时

• 它左边的子数组的数字之和就是从第一个数字开始累加到第i-1个数字的和
• 它右边的子数组的数字之和就是从第i+1个数字开始累加到最后一个数字的和,这个和等于数组中所有数字之和减去从第一个数字累加到第i个数字的和

代码实现


function pivotIndex(nums){
  let total =0;
  total =nums.reduce((pre,cur)=>pre+cur);
  let sum = 0;
  for(let i=0;i<nums.length;i++){
    sum+=nums[i];
    if(sum - nums[i] == total - sum){
      return i
    }
  }
  return -1;
}
复制代码

后记

分享是一种态度。

全文完，既然看到这里了，如果觉得不错，随手点个赞和“在看”吧。