JS算法探险之数组

前言

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

例如

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

1. 用 i&1来计算 i%2
2. 还处理了很多典型的算法题
   • 整数除法
   • 二进制加法 ==> N 进制加法
   • 前 n 个数字二进制中 1 的个数
   • 只出现一次的数字

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

闲话少叙，那就开始咯。

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

• 数组算法千千万，sum套路就那般
• 「类型」不同路不同，「正整数」双指针，其余尝试用Si
• 「正整数」分两类，同向/反向 双指针
  • 先处理right,根据条件移动left
  • sum/mult < target: 右移 (right++)
  • sum/mult > target: 右移 (left++)
  • 「指针left永远不会走到指针right的右边」 (left<=right)
  • sumVStarget, sum小，left++；sum大，right--
  1. 「数据有序」反向针，left为首right为尾(求两数之和)
  2. 「子数组」同向针，区域之「和」或「乘积」
• 「非正整数」用Si(前i个数据和)
  1. Sj-Si-1 为所求
  2. 找「次数」、「长度」 Map(sum,count/index)来辅助

❝奇怪的知识点： 1. 数组的本质是「对象」且为「异质对象」 2. JS 只支持一维数组，并不支持矩阵 ❞

文章概要

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

知识点简讲

JS数组的本质

JS数组本质上是「对象」

❝根据 EMMAScript规范，在JS中有两种对象 1. 常规对象Ordinary Object 2. 异质对象Exotic Object ❞

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

而数组就是异质对象，即

❝数组的本质是「对象」且为「异质对象」 ❞

调用Array函数生成数组实例

ArrayCreate返回值

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的二维数组(矩阵)。

matrix(5,4)

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

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

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）直接的大小关系。 「left/right的移动方向是相反的」
   1. sum < target: 右移 left (left++)
   2. sum > target: 左移 right (right--)
2. 「方向相同」的双指针用来求「正数数组」中「子数组」的「和」(sum)或者「乘积」（mult）。 「初始化」的时候两个指针left/right都指向数组的「第一个」数字。 如果两个指针之间的「子数组」的sum或者mult与target之间关系如下： 「left/right的移动方向是相同的」
   1. sum/mult < target: 右移 right（right++）,在「子数组右边」增加新的数字
   2. sum/mult > target: 右移left(left++)，删除「子数组最左边」的数字

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: 右移left(left++)，删除「子数组最左边」的数字，子数组长度-1
   2. sum < target: 右移 right（right++）,在「子数组右边」增加新的数字，子数组长度+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: 右移left(left++)，删除「子数组最左边」的数字，子数组长度-1(mult变小)
   2. mult < target: 右移 right（right++）,在「子数组右边」增加新的数字，子数组长度+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. 累加数组数字求子数组之和 （Si）

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

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

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

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

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

1. 和为target的子数组

题目描述：

❝输入一个「整数」组成的数组和一个整数target,找出数组中数字之和等于target的「连续子数组」的个数 示例：输入数组：[1,1,1],target的值为2 输出 2 ❞

分析

1. 求「连续子数组之和」，但是数组不是「正整数」，所以「同向双指针」作废
2. 双指针作废，那我们就采用前i个数字之和的处理方式
   • 从头到尾扫描数组时，求「前i个数字之和」，并将和「保存」下来
   • 将数组的前i个数字之和记为x
   • 如果存在一个j (j<i) 即，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<i)之和也为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;
}