Home > 算法 > 求给定数组中区间和绝对值最小的区间长度

求给定数组中区间和绝对值最小的区间长度

求给定数组中区间和绝对值最小的区间长度

解法:

设每一个元素为ai

则,新开一数组,si = sigma(a1…ai)

再二重循环求绝对值最小的si-sj

时间复杂度O(n^2), 空间复杂度O(n)

update at 11-11, nlogn的方法

其实仔细一想,si这个数组是可以对它排一次序,然后求前后两个元素的差,得出来的就是最接近的。

这里面排序的性质是神奇的。真的很强大

Categories: 算法 Tags:
  1. jzemily622
    November 10th, 2010 at 13:08 | #1

    有O(n)的吧,就像求一个数组里面连续子串最大和

    • AttaCKovER
      November 10th, 2010 at 16:52 | #2

      请大牛指教。。。

  1. No trackbacks yet.
805
805