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

记录题目：

• 长度最小的子数组
• 螺旋矩阵 II
• 区间和

---

给定一个含有 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²) 通常涉及双重循环进行配对或区间遍历。

• 双指针时间复杂度：O(N) 快慢指针或首尾夹逼只需一次遍历即可处理问题。

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

• 暴力解法时间复杂度：O(N²) 枚举所有区间，逐个求和或判断。

• 滑动窗口时间复杂度：O(N) 利用窗口移动时的状态维护，只需遍历一次。

模拟行为：

• 主要原则：循环不变量原则 每一步操作都保持某种不变量成立，确保逻辑的正确性。

前缀和：

• 主要用途：减少重复计算，提高区间求和效率。

• 用途一：求数组前 i 个数之和 通过维护前缀和数组 sum[i] = nums[0] + ... + nums[i-1]。

• 用途二：求任意区间 [i, j] 的和 使用公式 sum[j+1] - sum[i] 实现 O(1) 查询。