求给定数组中区间和绝对值最小的区间长度
求给定数组中区间和绝对值最小的区间长度
解法:
设每一个元素为ai
则,新开一数组,si = sigma(a1…ai)
再二重循环求绝对值最小的si-sj
时间复杂度O(n^2), 空间复杂度O(n)
update at 11-11, nlogn的方法
其实仔细一想,si这个数组是可以对它排一次序,然后求前后两个元素的差,得出来的就是最接近的。
这里面排序的性质是神奇的。真的很强大
Categories: 算法
求给定数组中区间和绝对值最小的区间长度
解法:
设每一个元素为ai
则,新开一数组,si = sigma(a1…ai)
再二重循环求绝对值最小的si-sj
时间复杂度O(n^2), 空间复杂度O(n)
update at 11-11, nlogn的方法
其实仔细一想,si这个数组是可以对它排一次序,然后求前后两个元素的差,得出来的就是最接近的。
这里面排序的性质是神奇的。真的很强大
有O(n)的吧,就像求一个数组里面连续子串最大和
请大牛指教。。。