5. 数组三等分

来源：腾讯 WXG 一面

题目

将数组尽可能平均地分成三份，返回每份的起始和结束下标。

代码

// 数组三等分，返回下标
// 腾讯WXG一面

const arr = [1, 2, 3, 4, 5, 6, 7]

function splitThree(arr){
    const len = arr.length;
    const size = Math.floor(len / 3);
    const re = len % 3;
    const result = [];
    let start = 0;
    for(let i = 0; i < 3; i++){
        const partSize = size + (i < re ? 1 : 0)
        const end = start + partSize - 1;
        result.push([start, end]);
        start += partSize;
    }
    return result;
}

console.log(splitThree(arr));

思路

使用贪心算法分配余数：

计算数组长度 len
计算每份的基础大小 size = Math.floor(len / 3)
计算余数 re = len % 3
将余数分配给前 re 份（每份多分配 1 个元素）
遍历 3 次，计算每份的起始和结束下标：
- 当前份的大小 = size + (i < re ? 1 : 0)
- 结束下标 = 起始下标 + 当前份大小 - 1
- 更新下一份的起始下标

关键点

余数最多为 2，分配给前面的份数，使分配尽可能平均
例如长度为 7 的数组，分成 [3, 2, 2] 而不是 [2, 2, 3]
使用 start 变量累加，确保下标连续不重叠
时间复杂度 $O (1)$ （固定循环 3 次）
空间复杂度 $O (1)$

5. 数组三等分 ​

题目 ​

代码 ​

思路 ​

关键点 ​

5. 数组三等分

题目

代码

思路

关键点