175 lines
4.9 KiB
Markdown
175 lines
4.9 KiB
Markdown
---
|
||
title: 数组
|
||
description:
|
||
published: true
|
||
date: 2024-03-21T11:15:46.175Z
|
||
tags: 算法
|
||
editor: markdown
|
||
dateCreated: 2024-03-21T11:15:46.175Z
|
||
---
|
||
|
||
# 二分法
|
||
```ts
|
||
function search(nums: number[], target: number): number {
|
||
let left:number = 0;
|
||
let right:number = nums.length - 1;
|
||
while (left <= right) {
|
||
let mid:number = left + ((right - left) >> 1);
|
||
if (nums[mid] < target) {
|
||
left = mid + 1;
|
||
} else if (nums[mid] > target) {
|
||
right = mid - 1;
|
||
} else {
|
||
return mid;
|
||
}
|
||
}
|
||
return -1;
|
||
};
|
||
```
|
||
# 移除元素
|
||
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
|
||
```ts
|
||
function removeElement(nums: number[], val: number): number {
|
||
let fast: number = 0, slow: number = 0;
|
||
while (fast < nums.length) {
|
||
if (nums[fast] !== val) {
|
||
nums[slow++]=nums[fast]
|
||
}
|
||
fast++;
|
||
}
|
||
return slow;
|
||
};
|
||
```
|
||
# 有序数组的平方
|
||
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
|
||
|
||
示例 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]
|
||
```ts
|
||
function sortedSquares(nums: number[]): number[] {
|
||
let resArr: number[] = [];
|
||
let i: number = 0, j: number = nums?.length - 1;
|
||
while (i <= j) {
|
||
if (Math.abs(nums[i]) >= nums[j]) {
|
||
resArr.unshift(nums[i] ** 2)
|
||
i++;
|
||
} else {
|
||
resArr.unshift(nums[j] ** 2)
|
||
j--;
|
||
}
|
||
}
|
||
return resArr;
|
||
};
|
||
```
|
||
# 长度最小的子数组
|
||
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
|
||
|
||
示例：
|
||
|
||
输入：s = 7, nums = [2,3,1,2,4,3]
|
||
输出：2
|
||
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
|
||
```ts
|
||
function minSubArrayLen(target: number, nums: number[]): number {
|
||
let res: number = nums.length + 1;
|
||
let sum: number = 0;
|
||
let i: number = 0;
|
||
for (let j = 0; j < nums?.length; j++) {
|
||
sum += nums[j];
|
||
if (sum >= target) {
|
||
while (sum - nums[i] >= target) {
|
||
sum -= nums[i++];
|
||
}
|
||
res = Math.min(res, j - i + 1);
|
||
}
|
||
}
|
||
return res === nums.length + 1 ? 0 : res;
|
||
};
|
||
```
|
||
# 螺旋矩阵II
|
||
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
|
||
|
||
示例:
|
||
|
||
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
|
||
```ts
|
||
function generateMatrix(n: number): number[][] {
|
||
let di: number = 0;
|
||
const res: number[][] = new Array(n).fill(1).map(i => new Array(n));
|
||
let num = 1;
|
||
while (di <= n >> 1) {
|
||
for (let j: number = di; j < n - di - 1; j++) {
|
||
res[di][j] = num++;
|
||
}
|
||
for (let j: number = di; j < n - di - 1; j++) {
|
||
res[j][n - di - 1] = num++;
|
||
}
|
||
for (let j: number = n - di - 1; j > di; j--) {
|
||
res[n - di - 1][j] = num++;
|
||
}
|
||
for (let j: number = n - di - 1; j > di; j--) {
|
||
res[j][di] = num++;
|
||
}
|
||
di++
|
||
}
|
||
if (n % 2 === 1) {
|
||
res[di - 1][di - 1] = num;
|
||
}
|
||
return res;
|
||
};
|
||
```
|
||
# 三数之和
|
||
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
|
||
|
||
注意： 答案中不可以包含重复的三元组。
|
||
|
||
示例：
|
||
|
||
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
|
||
|
||
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
|
||
```ts
|
||
function threeSum(nums: number[]): number[][] {
|
||
nums.sort((a, b) => a - b);
|
||
let length = nums.length;
|
||
let left: number = 0,
|
||
right: number = length - 1;
|
||
let resArr: number[][] = [];
|
||
for (let i = 0; i < length; i++) {
|
||
if (nums[i]>0) {
|
||
return resArr; //nums经过排序后，只要nums[i]>0, 此后的nums[i] + nums[left] + nums[right]均大于0,可以提前终止循环。
|
||
}
|
||
if (i > 0 && nums[i] === nums[i - 1]) {
|
||
continue;
|
||
}
|
||
left = i + 1;
|
||
right = length - 1;
|
||
while (left < right) {
|
||
let total: number = nums[i] + nums[left] + nums[right];
|
||
if (total === 0) {
|
||
resArr.push([nums[i], nums[left], nums[right]]);
|
||
left++;
|
||
right--;
|
||
while (nums[right] === nums[right + 1]) {
|
||
right--;
|
||
}
|
||
while (nums[left] === nums[left - 1]) {
|
||
left++;
|
||
}
|
||
} else if (total < 0) {
|
||
left++;
|
||
} else {
|
||
right--;
|
||
}
|
||
}
|
||
}
|
||
return resArr;
|
||
};
|
||
``` |