JavaScript如何将数组拆分为3个元素和近似相等的子数组

问题背景 #

需要将给定数组拆分为3个元素和近似相等的子数组，现有实现仅能按固定长度切分数组，未对子数组元素和做均衡调整，无法满足需求。

• 示例输入：[8, 1, 5, 2, 4, 1, 9, 8]
• 期望输出（子数组和偏差不超过1）：

[9, 2, 1, 1] // 和为13
[8, 4] // 和为12
[8, 5] // 和为13

• 原有固定切分的问题代码：

const items = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

const n = 3
const result = [[], [], []]

const x= Math.ceil(items.length / 3)

for (let line = 0; line < n; line++) {
  for (let i = 0; i < x; i++) {
    const value = items[i + line * x]
    if (!value) continue 
    result[line].push(value)
  }
}

console.log(result);

实现方案 #

采用贪心策略实现均衡拆分，逻辑简单效率高，完全满足近似相等的需求：

• 先将原数组降序排序，优先分配数值大的元素，避免大元素集中导致和偏差过大
• 遍历排序后的元素，每次将当前元素放到当前元素和最小的子数组中
• 遍历完成后即可得到和近似相等的3个子数组

完整代码 #

/**
 * 将数组拆分为指定数量的和近似相等的子数组
 * @param {number[]} items 输入数组
 * @param {number} groupCount 拆分的子数组数量，默认3
 * @returns {{result: number[][], sumArr: number[]}} 拆分结果+每个子数组的和
 */
function splitBalanced(items, groupCount = 3) {
  const result = Array.from({ length: groupCount }, () => []);
  const groupSums = new Array(groupCount).fill(0);
  // 降序排序，优先处理大元素
  const sortedItems = [...items].sort((a, b) => b - a);

  for (const num of sortedItems) {
    // 找到当前和最小的分组索引
    let minIdx = 0;
    for (let i = 1; i < groupCount; i++) {
      if (groupSums[i] < groupSums[minIdx]) minIdx = i;
    }
    // 插入元素并更新和
    result[minIdx].push(num);
    groupSums[minIdx] += num;
  }

  return { result, sumArr: groupSums };
}

// 测试示例输入
const demoInput = [8, 1, 5, 2, 4, 1, 9, 8];
const { result: demoRes, sumArr: demoSum } = splitBalanced(demoInput);
console.log('示例输入拆分结果：');
demoRes.forEach((arr, i) => console.log(arr, `// 和为${demoSum[i]}`));

// 测试原有测试用例
const testInput = [1,2,3,4,5,6,7,8,9,10];
const { result: testRes, sumArr: testSum } = splitBalanced(testInput);
console.log('\n原有测试数组拆分结果：');
testRes.forEach((arr, i) => console.log(arr, `// 和为${testSum[i]}`));

运行结果说明 #

1. 示例输入运行后输出和期望完全一致，三个子数组和为13、12、13
2. 原有测试数组拆分后三个子数组和为19、18、18，均衡度远高于固定长度切分的结果

注：该方案为近似最优解，时间复杂度为O(n)（分组数固定为3时），适合绝大多数业务场景。如果需要精确的和完全相等的拆分，需要使用动态规划实现，时间复杂度会大幅升高，非特殊需求不推荐使用。

内容的提问来源于stack exchange，提问作者user19300917