以下是 LeetCode LCP 14. 切分数组 的 JavaScript 实现。题目回顾给定一个整数数组 nums将其切割成若干个非空子数组使得每个子数组最左边的数和最右边的数的最大公约数大于 1。求最少可以切成多少个子数组。- 1 nums.length 10^5- 2 nums[i] 10^6解题思路核心思路是动态规划 质因数分解1. 预处理最小质因数用线性筛预处理 1~10^6 范围内每个数的最小质因数方便后续快速分解质因数。2. DP 状态定义- pre处理完前 i-1 个数的最少切割数- f[p]记录以质因数 p 为连接点时前若干个数的最少切割数3. 状态转移对于当前数 x有两种选择- 独自成段pre 1- 与前面某个以相同质因数为连接点的段合并f[p] 14. 更新分解 x 的所有质因数更新对应 f[p] 的值。时间复杂度O(n \cdot \log M)其中 M 10^6空间复杂度O(M)JavaScript 实现javascript/*** param {number[]} nums* return {number}*/var splitArray function(nums) {const MAX 1000001;// 预处理最小质因数 minPrime[i] 表示 i 的最小质因数const minPrime new Array(MAX).fill(0);for (let i 2; i MAX; i) {if (minPrime[i] 0) {minPrime[i] i;if (i * i MAX) {for (let j i * i; j MAX; j i) {if (minPrime[j] 0) {minPrime[j] i;}}}}}// f[p] 表示以质因数 p 为连接点时前若干个数的最少切割数const f new Map(); // 用 Map 存储只记录出现过的质因数let pre 0; // 前 i-1 个数的最少切割数for (let x of nums) {// 当前数独自成段或者与前面合并let cur pre 1;// 分解 x 的所有质因数let temp x;const primeFactors new Set();while (temp 1) {const p minPrime[temp];primeFactors.add(p);while (temp % p 0) {temp Math.floor(temp / p);}}// 尝试与前面以相同质因数结尾的段合并for (const p of primeFactors) {if (f.has(p)) {cur Math.min(cur, f.get(p) 1);}}// 更新 f[p]当前位置可以作为后续相同质因数的连接点for (const p of primeFactors) {if (f.has(p)) {f.set(p, Math.min(f.get(p), pre));} else {f.set(p, pre);}}pre cur;}return pre;};优化版本更接近官方题解以下是参考官方题解思路、使用更简洁的写法javascript/*** param {number[]} nums* return {number}*/var splitArray function(nums) {const N 1000001;// 线性筛预处理最小质因数const minPrime new Array(N).fill(0);const primes [];for (let i 2; i N; i) {if (minPrime[i] 0) {minPrime[i] i;primes.push(i);}for (let j 0; j primes.length i * primes[j] N; j) {minPrime[i * primes[j]] primes[j];if (i % primes[j] 0) break;}}// f[p] 记录以质因数 p 结尾的最小段数const f new Map();let pre 0; // 前 i 个数的最少段数for (const x of nums) {let cur pre 1; // 默认独自成段// 分解质因数let t x;const factors new Set();while (t 1) {const p minPrime[t];factors.add(p);while (t % p 0) t Math.floor(t / p);}// 尝试合并for (const p of factors) {if (f.has(p)) {cur Math.min(cur, f.get(p) 1);}}// 更新 ffor (const p of factors) {f.set(p, Math.min(f.get(p) || Infinity, pre));}pre cur;}return pre;};示例验证输入 输出 解释[2,3,3,2,3,3] 2 [2,3,3,2] (gcd2) 和 [3,3] (gcd3)[2,3,5,7] 4 每个数独自成段因为两两互质关键点总结1. 质因数分解是核心两个数能连接当且仅当它们有公共质因数。2. Map 优化空间不需要开 10^6 大小的数组只用 Map 记录出现过的质因数。3. 线性筛预处理O(M) 预处理最小质因数之后每次分解只需 O(\log x)。