一维整形数组，能否在 O(n) 时间内求其中连续子序列的绝对值的最小值
【一维整形数组，能否在 O(n) 时间内求其中连续子序列的绝对值的最小值】 请问，是连续子序列和的绝对值 还是 绝对值的和 最小？
■网友
可以。任意子段和都是两个前缀和之差，那么绝对值最小子段和就相当于前缀数组两两之差中绝对值最小者。求出前缀和数组，既然是整型，就用个桶排算法O(n)将其排序，然後O(n)遍历扫出相邻差最小的，即答案。
■网友
是想到一个nlogn的 先求出所有的前缀和 把前缀和排序 然后找出所有相邻两个数的差的最小值
■网友
额只想到O(nlogn)。想到了leetcode 327 Count of Range Sum那题，给定一个区间，求数组内有多少个子区间和在该范围内。这题应该类似，先不在意绝对值，将问题转化为只求最接近于零的子区间和。该问题在leetcode上面的解法总体来说有两种，一种是segment tree或bit，另一种是sum数组，二分查找，均是O(nlogn)的算法。
推荐阅读
- C语言 指针引用数组的地址问题
- 整形|男星整形失败，肿成猪头鼻子发臭，有固定女友还约见上百位女网友
- 整形|北京一演员花6万7整形，术后3天鼻尖多出一个洞，护士：只是结痂
- C语言多维数组声明调用和c为啥差别这么大
- 南京|下巴被整歪、腹部变坑洼，南京康美整形医院频遭投诉
- |梁溪大桥外观提升 贡湖大道井盖换新 百余道桥“整形美颜”扮靓城市
- 女士■女子整形后鼻子歪了！院方称可修复，他们私自存了肋骨
- 『』 上了ECMO才脱险 阅颜美容医院：如系院方责任不会推卸|解忧帮 女子整形进了ICU
- 江苏21岁女孩整形意外死亡整形机构被行政立案
- 警惕“免费整形模特”陷阱 谨慎使用个人信用贷款