LintCode问题图解-19

本文准备讲解1个算法编程问题， 这个算法编程问题来自LintCode平台。不了解.LintCode平台的读者可以阅读笔者文章（在线编程平台推荐-LeetCode）。问题的英文版本描述如下：

Subarray Sum

Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

Example

Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4].

子数组元素求和

给定一个整数数组，找到一个所有元素的和最接近于零的子数组。返回子数组第一个元素和最后一个元素的下标。代码应该返回满足要求子数组的起始位置和结束位置。

样例

给出 [-3, 1, 1, -3, 5]，返回 [0, 2]，[1, 3]，[1, 1]，[2, 2] 或者 [0, 4]。

该问题需要应用 Prefix Sum 方案。Prefix Sum 方案指对应原数组生成1个算法数组，这个算法数组用于记录数组元素的和。对于样例数组 [-3, 1, 1, -3, 5]，算法数组为 [-3, -3+1, -3+1+1, -3+1+1-3, -3+1+1-3+5]。对应任意的子数组, 处理算法数组的元素可以获得所有元素的和。对应任意的子数组, 处理算法数组的元素获得所有元素的和都仅需要1次运算。该问题应用 Prefix Sum 方案以后，变化为这样的问题：寻找2个最接近的算法数组元素。

简单的算法