代码随想录算法训练营第2天｜数组Part02

给定一个含有 n 个正整数的数组和一个正整数 target。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。

LeetCode209. 长度最小的子数组

• 同样是双指针，滑动窗口是暴力解法的优化。
• 通过 x === Infinity 或 x === -Infinity 判断是否为无穷值。
• 滑动窗口的时间复杂度：每个元素在滑动窗后进来操作一次，出去操作一次，所以时间复杂度是 2 × n 也就是O(n)。

给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix。

LeetCode59. 螺旋矩阵 II

两种创建二维数组方法的对比：

两种创建二维数组（生成 n×m 矩阵）的方法对比：

方法	new Array(n).fill(0).map(() => new Array(m).fill(0))	Array.from({ length: n }, () => new Array(m).fill(0))
初始化方式	先生成一维数组并填充，再用 map 替换为长度为 m 的子数组	从类数组对象生成，回调函数创建长度为 m 的子数组
空槽处理	fill(0) 确保每个元素非空，map 可正常执行	不存在空槽问题，直接遍历索引
性能	多一次 fill(0)，性能略低	略优，略微更简洁高效
兼容性	ES6+，现代浏览器与 Node.js 支持	ES6+，兼容性相同

题目描述：给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述：第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。

输出描述：输出每个指定区间内元素的总和。

LeetCode58. 区间和

Node.js 输入输出处理详解

// 引入 readline 模块，用于逐行读取标准输入
const readline = require("readline");

// 创建接口：绑定标准输入输出
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const inputs = []; // 用于存储所有输入的行

// 每读入一行，就推入数组
rl.on("line", (line) => {
    inputs.push(line.trim());
});

// 所有输入读取完毕后触发此事件（如 Ctrl+D），在这里处理逻辑
rl.on("close", () => {
    // 你可以在这里处理所有读取完的数据
    // 示例：处理第1行数字、第2行数组
    const n = parseInt(inputs[0]);
    const arr = inputs[1].split(" ").map(Number);

    // 处理结果并输出
    // console.log("n =", n);
    // console.log("arr =", arr);

    const res = deal(inputs);
    // 打印结果
    console.log(res);
});

// 对传入的数据进行处理
function deal(inputs) {
    // ...
    return res;
}

Node.js 输入处理的核心步骤

1. 创建读取接口：readline.createInterface() 绑定标准输入输出流
2. 监听 line 事件：逐行读取输入，存入数组等数据结构
3. 监听 close 事件：在输入结束后处理数据
4. 数据解析：将字符串转换为数值、数组等类型，根据需求进行处理

数组经典题型

二分法查找

• 暴力解法时间复杂度：O(N)
• 二分法时间复杂度：O(LogN)

双指针法（例如：快慢指针法）

• 暴力解法时间复杂度：O(N^2)
• 双指针时间复杂度：O(N)

滑动窗口（本质为双指针法的一种）

• 暴力解法时间复杂度：O(N^2)
• 滑动窗口时间复杂度：O(N)

模拟行为

重要原则：循环不变量原则。

前缀和

重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数。

• 用途一：求数组前 i 个数之和

• 用途二：求数组的区间和