数组
基础知识
数组概念
定义：数组是存放在连续内存空间上的相同类似数据的集合。
数组可以方便的通过下标索引的方式获取到下标对应的数据。
需要注意的点：
- 数组下标是从0开始的，因为索引是记录数组元素在数组中的偏移量，例如，数组第一个元素在数组中的偏移量是0
- 数组内存空间的地址是连续的。
因为数组在内存空间中的地址是连续的，所以我们在删除或者添加元素的时候，就难免要移动其他元素的地址。
操作数组的方法
二分查找
二分查找是一种基于分治策略的高效搜索算法。利用数据的有序性，每次缩小一半的搜索范围，直到找到目标元素。
二分法的前提条件是：数组必须是有序数组。
核心思想：
初始化指针i = 0和j = n -1，分别指向数组首元素和尾元素，代表搜索区间[0,n-1]。其边界包含值本身。
然后按以下思路编写代码：
计算中点索引值
计算结果向下取整。
判断终点处元素的大小和目标
target的关系，分为三种情况：- 当
nums[m]<target时，说明target在区间[m+1,j]中，因此执行i = m + 1 - 当
nums[m]>target时，说明target在区间[i,m+1]中，因此执行j = m -1 - 当
nums[m]=target，说明找到target，返回索引m
- 当
滑动窗口
滑动窗口就是：不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。
例题：
INFO
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例1:二分查找
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4代码实现及解析：
function search(nums: number[], target: number): number {
//初始化指针
let i = 0,j = nums.length - 1
while (i <= j) {
//计算中点索引
//为什么要在迭代中计算中点，因为在每次迭代之后i,j指针会变化，所以需要重新计算中点索引
let m = Math.floor((i + j) / 2)
//判断三种情况
if (nums[m] < target) i = m + 1
else if (nums[m] > target) j = m - 1
else return m
}
return -1
}示例2:移除元素
INFO
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需要考虑数组中超出新长度后面的元素。
使用双指针法进行求解：
/**
* 双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
* 定义快慢指针
* 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
* 慢指针：指向更新 新数组下标的位置
* @param nums
* @param val
* @returns
*/
function removeElement(nums: number[], val: number): number {
let k = 0
for (let i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[k++] = nums[i]
}
}
return k
}示例2:有序数组的平方
INFO
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
双指针法求解：
function sortedSquares(nums: number[]): number[] {
const helper: number[] = []
let left = 0,right = nums.length - 1
while (left <= right) {
// 右侧的元素不需要取绝对值，nums 为非递减排序的整数数组
// 在同为负数的情况下，左侧的平方值一定大于右侧的平方值
if (Math.abs(nums[left]) > nums[right]) {
// 使用 Array.prototype.unshift() 直接在数组的首项插入当前最大值
helper.unshift(nums[left] ** 2)
left++
} else {
helper.unshift(nums[right] ** 2)
right--
}
}
return helper
}示例3:长度最小的子数组
INFO
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
带式示例：
function minSubArrayLen(target: number, nums: number[]): number {
let left: number = 0,
res: number = Infinity,
subLen: number = 0,
sum: number = 0
for (let right: number = 0; right < nums.length; right++) {
sum += nums[right]
//当满足集合的和大于目标值的时候移动起始指针
while (sum >= target) {
//满足集合的和大于目标值的时候，记录子数组的长度
subLen = right - left + 1
res = Math.min(res, subLen)
sum -= nums[left]
//移动起始指针
left++
}
}
return res === Infinity ? 0 : res
}示例4:螺旋矩阵
INFO
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
代码示例：
function generateMatrix(n: number): number[][] {
let loopNum: number = Math.floor(n / 2);
const resArr: number[][] = new Array(n).fill(1).map(i => new Array(n));
let chunkNum: number = n - 1;
let startX: number = 0;
let startY: number = 0;
let value: number = 1;
let x: number, y: number;
while (loopNum--) {
x = startX;
y = startY;
while (x < startX + chunkNum) {
resArr[y][x] = value;
x++;
value++;
}
while (y < startY + chunkNum) {
resArr[y][x] = value;
y++;
value++;
}
while (x > startX) {
resArr[y][x] = value;
x--;
value++;
}
while (y > startY) {
resArr[y][x] = value;
y--;
value++;
}
startX++;
startY++;
chunkNum -= 2;
}
if (n % 2 === 1) {
resArr[startX][startY] = value;
}
return resArr;
};