#2035. 将数组分成两个数组并最小化数组和的差

• LeetCode：原题1
• 难度：困难
• 归类：滑动窗口+双指针（位运算、数组、双指针、二分查找、动态规划、位掩码、有序集合、排序）
• 主解法：方法一

#先给结论

这道题的核心是利用有序性或答案单调性，每轮排除一半不可能成为答案的候选区间。面试时先说清楚“状态表示什么、为什么能排除其他候选、何时更新答案”，再写代码；只报出“用 二分查找”还不足以证明理解。

#题目描述

题目要求完成“将数组分成两个数组并最小化数组和的差”。输入包括 nums（integer[]），需要返回 integer。完整限制以原题为准，解题时重点利用这些特征：位运算、数组、双指针、二分查找、动态规划、位掩码、有序集合、排序。

示例：

输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。

#题型判断

本题使用 二分查找：利用有序性或答案单调性，每轮排除一半不可能成为答案的候选区间。

#指针含义

维护仍可能包含答案的搜索区间，比较中点后只保留满足题意的一侧。代码中的 left、right、slow、fast 只承担各自定义的职责，不能在循环中临时改变语义。

#窗口或区间维护规则

根据中点是否满足条件移动左、右边界；边界定义和循环条件必须配套。始终保持：循环开始时，答案如果存在，一定仍在当前候选区间中。

以示例为主线：

输入：nums = [3,9,7,3]
输出：2
解释：最优分组方案是分成 [3,9] 和 [7,3] 。
数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。

先建立最小初始区间，再按代码的判断扩张或收缩；指针越过的部分已经完成证明，所以无需回退。

#答案更新时机

更新答案前先确认当前区间是否满足题意。求最长合法区间时通常在恢复合法后更新；求最短合法区间时通常在合法期间先更新再继续收缩；固定长度窗口则在长度达到要求后更新。

#边界条件与易错点

• 空输入、单元素、所有元素相同，以及没有合法答案。
• 最容易错在开闭区间混用、边界没有越过 mid，以及重复元素下没有继续收缩。
• 窗口长度使用闭区间时是 right - left + 1，不要与左闭右开区间混用。

#代码实现

参考实现来源：JoshCrozier/leetcode-javascript，按本文结构重新整理；原项目采用 MIT License。

#JavaScript 实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDifference = function(nums) {
  const n = nums.length / 2;
  let result = Infinity;
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
  const firstHalfSubsets = new Map();

  for (let mask = 0; mask < (1 << n); mask++) {
    let size = 0;
    let subsetSum = 0;

    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) !== 0) {
        size++;
        subsetSum += nums[i];
      }
    }

    if (!firstHalfSubsets.has(size)) {
      firstHalfSubsets.set(size, []);
    }
    firstHalfSubsets.get(size).push(subsetSum);
  }

  for (const [size, sums] of firstHalfSubsets) {
    sums.sort((a, b) => a - b);
  }

  for (let mask = 0; mask < (1 << n); mask++) {
    let size = 0;
    let secondHalfSum = 0;

    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) !== 0) {
        size++;
        secondHalfSum += nums[n + i];
      }
    }

    const complementSize = n - size;
    const firstHalfSums = firstHalfSubsets.get(complementSize);
    const target = (totalSum - 2 * secondHalfSum) / 2;
    const closestIndex = binarySearch(firstHalfSums, target);

    if (closestIndex < firstHalfSums.length) {
      result = Math.min(
        result, Math.abs(totalSum - 2 * (secondHalfSum + firstHalfSums[closestIndex]))
      );
    }

    if (closestIndex > 0) {
      result = Math.min(
        result, Math.abs(totalSum - 2 * (secondHalfSum + firstHalfSums[closestIndex - 1]))
      );
    }
  }

  return result;
};

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  if (right < 0) return 0;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}

#代码与思路对照

读代码时应把每个判断还原成“它排除了什么状态或完成了哪次转移”，而不是只记变量名。

#复杂度分析

• 时间复杂度：O(log U × C)，U 为搜索范围，C 为一次可行性检查的成本。
• 空间复杂度：O(n)，用于辅助状态或递归栈。

复杂度必须按“状态数量 × 每个状态处理成本”分析；如果存在排序、堆操作、递归深度或结果数组，需要单独计入，不能只看最外层循环。

#面试官递进追问

#1. 为什么本题适合 二分查找？

因为利用有序性或答案单调性，每轮排除一半不可能成为答案的候选区间。 为什么问： 检查你是在识别性质，还是只凭题号背模板。回答要抓住可被利用的单调性、重复子问题或数据结构约束。

#2. 代码维护的核心状态是什么？

维护仍可能包含答案的搜索区间，比较中点后只保留满足题意的一侧。 为什么问： 状态定义决定代码是否可证明。回答时要让每个变量都能对应到题意。

#3. 这个实现依赖什么不变量？

循环开始时，答案如果存在，一定仍在当前候选区间中。 为什么问： 不变量比逐行复述代码更能证明理解，回答要说明它在初始化、推进和结束时都成立。

#4. 为什么这样推进不会漏掉答案？

根据中点是否满足条件移动左、右边界；边界定义和循环条件必须配套，被跳过的状态已经由题目性质证明不可能更优或已经处理完成。 为什么问： 检查正确性证明，重点不是“指针这样写”，而是“为什么可以排除”。

#5. 最危险的边界是什么？

最容易错在开闭区间混用、边界没有越过 mid，以及重复元素下没有继续收缩。 为什么问： 检查代码能否一次通过，回答要给出具体失败场景而不是只说“注意边界”。

#6. 复杂度还能优化吗？

先看瓶颈来自状态数量、每次转移成本还是辅助结构操作；只有其中一项能被减少时，复杂度才可能继续下降。 为什么问： 检查你能否从成本组成出发优化，而不是机械背最优复杂度。

#7. 如果输入规模扩大或数据改成流式，方案怎么变？

要判断当前算法是否需要随机访问全部输入；若只依赖有限历史状态，可以做滚动或在线维护，否则需要分块、外存或调整数据结构。 为什么问： 检查算法理解能否迁移到工程约束。

#8. 有哪些替代解法，如何取舍？

可以从暴力枚举开始，再比较排序、哈希、搜索或动态规划等方案；取舍标准是时间、空间、是否修改输入和实现复杂度。 为什么问： 检查横向比较能力。回答要说明替代方案为什么更慢或在什么条件下更合适。

#常见错误回答

• “这题套 二分查找 模板即可”：只有结论，没有说明题目性质和排除依据。
• 逐行朗读代码：没有建立状态、不变量和正确性因果链。
• 只报 O(n) 或 O(n²)：没有解释每个状态被访问多少次，也容易漏掉排序或辅助结构。
• 把示例能跑通当成证明：示例只能帮助检查，不能覆盖重复值、空输入和极端边界。

#可迁移总结

• 核心关键词：二分查找、状态定义、不变量、推进规则、边界。
• 一句话本质：利用有序性或答案单调性，每轮排除一半不可能成为答案的候选区间。
• 思考链路：识别题目性质 → 定义状态 → 证明推进安全 → 确定更新时机 → 检查边界与复杂度。
• 1 分钟回答：说清题型、核心状态、推进规则和复杂度。
• 3 分钟回答：补上正确性依据、示例和两个关键边界。
• 10 分钟回答：写出代码，并比较替代方案、空间优化和工程限制。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 不看代码，你能用一句话说出本题的不变量吗？

2. 如果把示例中的重复值、空输入或边界值换掉，哪一行代码最先受到影响？

3. 不改变正确性的前提下，你能写出一种替代方案并比较复杂度吗？