题目
对一个长度为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
}
