Subarray Sum Closest
2016, Apr 28
Subarray Sum Closest
@(算法)[Subarray, Sort, Presum Array]
这一题怎样用一句话描述？
找出数组中和最接近0的子数组
用到什么算法？什么数据结构？
排序，数组
通过这题学到了什么？
暴力法肯定超时，参见这次提交的代码，不过要是连暴力法都想不出来就GG了。然后就是参见了这篇博客的方法，其实就是和Subarray Sum相同的思路，只不过这里要稍作改动：
- 先求出数组的presum数组（先序和数组），并且记录下标
- 按照sum从小到大排序
- 找出相邻元素的sum之差绝对值最小的一对，按照下标从小到大输出即可（注意：小的那个下标要+1，因为我们初始化presum[0] = (0, -1)，但是下标不可能为负数，所以要+1）
可能(已经)遇到的BUG有？
输出的小下标没有+1