含负数数组最小绝对差计算遇无限循环错误求助

问题根源 #

原代码未处理数组包含负数的场景，引发以下问题：

• 当数组存在负数时，总和sum可能为负，halfSum也变为负数，同时DP数组的第二维长度sum+1为负数，生成的是空数组，后续dp[n][j]始终为undefined。
• while循环从负数的halfSum开始递减，永远无法找到dp[n][j]为true的情况，触发无限循环，最终超出迭代次数限制报错。

修复后的代码 #

function minAbsDiff(nums) {
  const n = nums.length;
  const totalSum = nums.reduce((acc, val) => acc + val, 0);
  
  // 计算所有可能的子集和的最小值（全选负数）和最大值（全选正数）
  let minSum = 0;
  let maxSum = 0;
  for (const num of nums) {
    if (num < 0) {
      minSum += num;
    } else {
      maxSum += num;
    }
  }
  
  const offset = -minSum; // 偏移量，将最小子集和映射为0
  const possibleSumRange = maxSum - minSum;
  
  // 初始化DP数组：dp[i][s + offset] 表示前i个元素能否得到子集和s
  const dp = Array.from({ length: n + 1 }, () => Array.from({ length: possibleSumRange + 1 }, () => false));
  dp[0][offset] = true; // 前0个元素的子集和为0，对应索引0 + offset
  
  for (let i = 1; i <= n; i++) {
    const num = nums[i - 1];
    for (let s = minSum; s <= maxSum; s++) {
      const idx = s + offset;
      // 不选当前元素的情况
      dp[i][idx] = dp[i-1][idx];
      // 选当前元素的情况：检查s - num是否在合法子集和范围内
      const prevS = s - num;
      if (prevS >= minSum && prevS <= maxSum) {
        dp[i][idx] = dp[i][idx] || dp[i-1][prevS + offset];
      }
    }
  }
  
  // 遍历所有可能的子集和，找到最小绝对差
  let minDiff = Infinity;
  for (let s = minSum; s <= maxSum; s++) {
    if (dp[n][s + offset]) {
      const currentDiff = Math.abs(2 * s - totalSum);
      if (currentDiff < minDiff) {
        minDiff = currentDiff;
      }
    }
  }
  
  console.log(minDiff);
  return minDiff;
}

var x = [2,-1,0,4,-2,-9];
minAbsDiff(x); // 输出：0

关键改动说明 #

• 处理负数子集和：通过计算子集和的最小/最大值，引入偏移量将负数子集和映射为非负索引，确保DP数组能正常初始化和访问。
• 调整DP逻辑：DP数组记录所有可能的子集和（包括负数），通过偏移量转换为合法的数组索引，覆盖所有可能的子集情况。
• 替换循环逻辑：遍历所有可能的子集和计算最小绝对差，避免原while循环在负数场景下的无限迭代问题。

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