找出最接近零值的子数组(js实现)

题目

对一个长度为N的子数组，找到其最接近零值的子数组（子数组均是由连续元素组成）。要求时间复杂度为O(nlgn)

解决

sum(i) = arr[0]+arr[1]+...+arr[i];
则subArr(m,n) = sum(n) - sim(m)；

所以可以

• 先求得sum [i] (i从0到N-1)，(复杂度O(n) )
• 将其排序（ 快排的复杂度为O(nlgn) ）
• 计算相邻元素的绝对值( 复杂度O(n) )，最小值即为所求。

但别忘了我们是要找到最接近零值的子数组，所以在求得sum[i]时，以i 为key, sum[i]为value存为一个对象，此后都是基于value来比较。

// sumMap=[{id:i,value:sum[i]}]
function sumMap(arr){
  if (arr.length<2) {
    return arr;
  }
  let sumMap = [];
  sumMap[-1] = {value:0};
  for(let len = arr.length, i = 0; i < len; i++){
    let obj={};
    obj.id=i;
    obj.value = sumMap[i-1].value + arr[i]
    sumMap.push(obj)
  }
  return sumMap
}
let arr=[3,5,-4,9,-5,2,7,-5,1,-7,9,-4,3]

function findMinAbsSubArr(arr){

  // 从大到小排序
  let sortedSumArr = sumMap(arr).sort((a,b) => a.value < b.value ? 1: -1);
  let threshold = Number.MAX_VALUE;
  // 保证所有的零值子数组都获取到
  // 如果只需得到一个的话，直接使用一个对象保存最小结果即可。
  let minArr=[];

  for(let i=0, len = sortedSumArr.length; i<len-1; i++){
    let diff = sortedSumArr[i].value - sortedSumArr[i+1].value;
    // diff >= 0
    if (diff <= threshold) {
      threshold = diff;
      let obj = {
        index1:Math.min(sortedSumArr[i].id,sortedSumArr[i+1].id),
        index2:Math.max(sortedSumArr[i].id,sortedSumArr[i+1].id),
        diff:diff
      }
      minArr.push(obj);
    }
  }

  // 数组中的最后一个元素肯定是最接近零值的子数组，就看有几个相同diff值得。
  let result= [];
  let minimum = minArr[minArr.length-1].diff;
  while( minArr[minArr.length-1].diff == minimum){
    let lastItem = minArr.pop();
    result.push(arr.slice(lastItem.index1+1,lastItem.index2+1))
  }
  return result
}