TypeScript算法题实战——数组篇（二分法、双指针、滑动窗口、螺旋矩阵的TS解法）

TypeScript 是由微软开发的一款开源的编程语言，TypeScript 是 Javascript 的超集，遵循最新的 ES6、ES5 规范，TypeScript 扩展了 JavaScript 的语法。TypeScript 更像后端 Java、C#这样的面向对象语言，可以让 JavaScript 开发大型企业项目。谷歌也在大力支持 Typescript 的推广，谷歌的 angular2.x+ 就是基于 Typescript 语法，最新的 Vue 、React 也可以集成 TypeScript。Nodejs 框架中的 Nestjs、midway 中用的就是 TypeScript 语法。

本系列博文将通过一些力扣算法题目，边学习TypeScipt边实战算法，这篇将通过一些经典算法题熟悉TS语言数组的一些基本操作。

目录

零、常规数组操作

// arr 初始化let arr:Array<number>=newArray<number>();// let arr = [1, 2, 3];
 
arr =[1,2,3,7,5,9,1];// 给数组直接赋值console.log("数组", arr,"长度为:", arr.length);// 向数组中增加元素console.log("向数组 尾 添加一个元素4, 修改后的数组长度为: "+ arr.push(4));console.log("向数组 头 添加一个元素0, 修改后的数组长度为: "+ arr.unshift(0));console.log(arr);console.log("向数组下标为2插入 一个 元素 99: "+ arr.splice(2,0,99));console.log(arr);console.log("向数组下标为2插入 3个 元素 88,77,66: "+ arr.splice(2,0,88,77,66));console.log(arr);// 从数组中删除元素console.log("从数组 尾 删除一个元素: "+ arr.pop());console.log("从数组 头 删除一个元素: "+ arr.shift());console.log(arr);console.log("删除数组 下标为4 的元素: "+ arr.splice(4,1));console.log(arr);console.log("删除数组中从 下标为2开始后3个 元素: "+ arr.splice(2,3));console.log(arr);// 清空数组的几种方式
arr.length =0;
arr =[];// 只是更改数组的引用地址, 原数组内存将等待垃圾回收
arr.splice(0, arr.length);
 
arr =[1,2,3,7,5,9,1];// 获取数组中某个元素console.log("获取数组 下标为0 的元素: "+ arr[0]);console.log("获取数组 下标为100 的元素: "+ arr[100]);// 当该元素没有的时候, 会返回一个undefined类型// 修改数组中的某个元素
arr[0]=111;// arr[-10] = 0; // 我们可以给一个非法下标赋值, 且仍然不会报错, 但我们并不推荐这么做, 这样会把一个数组类型转换为复杂类型
arr[10]=999;// 当给一个超出当前数组长度的下标元素赋值时, 该数组将会自动补齐数组长度, 且中间未赋值的数组元素为undefined类型console.log(arr, arr[9], arr.length);// 查找console.log("从数组中查找 [元素为3] 的下标: ", arr.indexOf(3));console.log("从数组中查找 [元素为53] 的下标: ", arr.indexOf(53));// 当找不到时会返回-1console.log("数组中是否包含 值为3 的元素", arr.includes(3));// 查找数组中(从左往右)第一个大于5的数组元素let item:number= arr.find((val:number, index:number, array:Array<number>)=>{return val >5;});console.log("数组中(从左往右)第一个大于5的数组元素", item);// 查找数组中(从左往右)第一个大于5的数组元素的下标let index:number= arr.findIndex((val:number, index:number, array:Array<number>)=>{return val >5;});console.log("数组中(从左往右)第一个大于5的数组元素的下标", index);// 排序console.log("升序排列后的数组: ", arr.sort(function(a, b){return a - b}));console.log("降序排列后的数组: ", arr.sort(function(a, b){return b - a}));
 
arr =[1,99,88,111,200,4,5,7,222,555,30];console.log("按字符排序后的数组: ", arr.sort());console.log("反转数组顺序", arr.reverse());// 遍历数组for(let i:number=0; i < arr.length; i++){console.log(arr[i]);}for(let i in arr){console.log(`下标${i}, 元素${arr[i]}`);}for(let val of arr){console.log(`元素${val}`);}// 迭代数组
arr.forEach((val:number, index:number, arr:Array<number>)=>{console.log(`元素:${val}, 下标${index}, 数组本身${arr}`);});let delArr:Array<number>=[1,3,5,7,12,14,19,20,25,30];// 删除数组中符合条件的某几个元素let delTempArr:Array<number>=[];for(let i:number=0; i < delArr.length; i++){if(delArr[i]%2==0){
        delTempArr.push(delArr[i]);}}
delArr = delTempArr;console.log(delArr);// 获取一个新数组, 该数组中的元素值原数组值的10倍let arr1:Array<number>= arr.map((val:number, index:number, array:Array<number>)=>{return val *10;});console.log(arr1);// 获取一个新数组, 该数组中的元素为原数组中所有大于10的值let arr2:Array<number>= arr.filter((val:number, index:number, array:Array<number>)=>{return val >10;});console.log(arr2);console.log(arr);let sum = arr.reduce((total, val:number, index:number, array:Array<number>)=>{console.log(index, val, total);return total + val;});console.log("总和", sum);// 判断该数组是否 每个元素都大于0, 该方法一旦判定为假将不会再迭代let isHas:boolean= arr.every((val:number, index:number, array:Array<number>)=>{return val >0;});console.log("判断该数组是否 每个元素都大于0", isHas);// 判断该数组是否 每个元素都小于200let isHas0:boolean= arr.every((val:number, index:number, array:Array<number>)=>{console.log(val <200);return val <200;});console.log("判断该数组是否 每个元素都小于200", isHas0);// 判断该数组中是否 存在大于100的元素, 该方法一旦判定为真将不会再迭代let isHas1:boolean= arr.some((val:number, index:number, array:Array<number>)=>{console.log(val >100);return val >100;});console.log("该数组中是否存在大于100的元素", isHas1);// 连接两个数组到一个新数组let arr0 =[-1,2,4,6,7,999];let arrConcat:Array<number>= arr.concat(arr0);console.log("arr和arr0连接后的新数组", arrConcat);// 将数组元素填充为某个值, 可用作初始化数组let arr3:Array<number>=newArray<number>(10);
arr3.fill(1);console.log("数组每个元素初始化为1", arr3);// 将数组元素转换为字符串let arr4:Array<string>=["hello",",","my"," ","word!"];console.log("将数组元素转换为字符串", arr4.join(""),"用逗号连接成字符串", arr4.join(","));// 将字符串转换为数组let str:string="你好,我的朋友!";console.log(str.split(""));// 获取子数组let arr6 =["111","333","str","is","fff","sos"];console.log("下标从0到3的子数组", arr6.slice(0,4));

一、二分查找

力扣链接：https://leetcode.cn/problems/binary-search/

1.1、题目描述

给定一个 n 个元素有序的（升序）整型数组

nums

和一个目标值

target

，写一个函数搜索

nums

中的

target

，如果目标值存在返回下标，否则返回 -1。

1.2、示例

IO示例：

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

1.3、题解

数组为有序数组，同时题目还强调数组中无重复元素，所以可以直接用传统二分法。但是要注意的是 ts的

number

类型如

left: number

不是int类型，所有数字都是浮点数，而没有int或者float类型，所以我们需要使用

Math.floor()

向下取整。

functionsearch(nums:number[], target:number):number{let index:number=-1;let left:number=0;let right:number= nums.length -1;while(left <= right){let middle:number= Math.floor((left + right)/2);// Math.floor向下取整if(nums[middle]> target){
            right = middle -1;}elseif(nums[middle]< target){
            left = middle +1;}else{
            index = middle ;break;}}return index;};

二、移除元素

力扣链接：https://leetcode.cn/problems/remove-element/

2.1、题目描述

题目描述：给你一个数组

nums

和一个值

val

，你需要

原地

移除所有数值等于

val

的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并

原地

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

2.2、示例

示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

2.3、题解

使用双指针法：

functionremoveElement(nums:number[], val:number):number{let left:number=-1;let right:number=-1;let res:number=0;while(right < nums.length-1){
        right ++;if(nums[right]!= val){
            res ++;
            left ++;
            nums[left]= nums[right];}}return res;};

三、有序数组的平方

力扣链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

3.1、题目描述

给你一个按 非递减顺序 排序的整数数组

nums

，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

3.2、示例

示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

3.3、题解

先将数字乘以平方，数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。然后使用双指针。

functionsortedSquares(nums:number[]):number[]{let left:number=0;let right:number= nums.length-1;let res:number[]=[];for(let i:number=0; i < nums.length; i++){
        nums[i]= nums[i]* nums[i];}for(let i:number= nums.length -1; i >=0; i--){if(nums[left]< nums[right]){
            res[i]= nums[right];
            right --;}else{
            res[i]= nums[left];
            left ++;}}return res;};

四、长度最长的子数组

力扣链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

4.1、题目描述

给定一个含有

n

个正整数的数组和一个正整数

target

。

找出该数组中满足其和

≥ target

的长度最小的 连续子数组

[numsl, numsl+1, ..., numsr-1, numsr]

，并返回其长度。如果不存在符合条件的子数组，返回

0

。

4.2、示例

这里是引用
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

4.3、题解

使用滑动窗口法，本质上也是双指针的操作，tmplength记录滑动窗口目前的大小（用right-left其实也可以直接计算），sum记录滑动窗口当前的和值，minlength记录最小的窗口大小。

functionminSubArrayLen(target:number, nums:number[]):number{let left:number=0;let right:number=0;let minlength:number=-1;let sum:number=0;let tmplength:number=0;while(right < nums.length){
       sum = sum + nums[right];
       right ++;
       tmplength ++;while(sum >= target){if(minlength ==-1)
            minlength = tmplength;elseif(minlength > tmplength){
              minlength = tmplength;}
          sum = sum - nums[left];
          left ++;
          tmplength --;}}if(minlength ==-1)return0;return minlength;};

五、螺旋矩阵 II

力扣链接：https://leetcode.cn/problems/spiral-matrix-ii/

5.1、题目描述

给你一个正整数

n

，生成一个包含

1 到 n2

所有元素，且元素按顺时针顺序螺旋排列的

n x n

正方形矩阵

matrix

。

5.2、示例

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：
输入：n = 1
输出：[[1]]

5.3、题解

需要创建二维数组，这里使用到了Array在ts中的接口，使用方法可以详见：https://blog.csdn.net/qq_28550263/article/details/121201774
我们使用模拟法，模拟螺旋的形态：

functiongenerateMatrix(n:number):number[][]{let top:number=0;let bottom:number= n -1;let left:number=0;let right:number= n -1;const resArr:number[][]=newArray(n).fill(1).map(i =>newArray(n).fill(1));let k:number=1;while(k < n * n +1){for(let j = left; j <= right; j++, k++)//从左到右
            resArr[top][j]= k;
        top ++;for(let i = top; i <= bottom; i++, k++)//从上到下
            resArr[i][right]= k;
        right --;for(let j = right; j >= left; j--, k++)//从右到左
            resArr[bottom][j]= k;
        bottom --;for(let i = bottom; i>= top; i--, k++)//从下到上
            resArr[i][left]= k;
        left ++;}return resArr;};