数组利用前缀和求子数组问题

1、子数组之和
https://www.lintcode.com/problem/subarray-sum/description
描述
给定一个整数数组，找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置
至少有一个子数组的和为 0
您在真实的面试中是否遇到过这个题？ 是
题目纠错
样例
给出 [-3, 1, 2, -3, 4]，返回[0, 2] 或者 [1, 3].

解题思路：
问题分析：
这个问题比较好想的算法的时间复杂度是O(n^2)，这不是我们希望看到的。

要解决这个问题我觉得需要明白两点：

1.一个子数组的和为零，我们假设这个子数组是{ a[i], a[i+1], ..., a[j] },也就是a[i] + a[i+1] +...+ a[j] = 0,起始和结束位置其实就是i和j。那么 a[0] + a[1] +...+ a[i-1] + a[i] + a[i+1] +...+ a[j] = a[0] + a[1] +...+ a[i-1] 。把这个式子转换下，假如这个数组的前 i 项的和与前j项的和相等，那么i项到j项之间的数组的元素的和肯定是零。i，j就是需要的结果。

所以这个问题就转换成了求数组前n项和的问题

2.假如前 i 项的和为零，那么0 和 i 即为所求结果

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    vector<int> subarraySum(vector<int> &nums) {
        // write your code here
        vector<int> vecIndex;
        map<int, int> mapSum;
        int sum = 0;
        mapSum[0] = -1;//处理从0开始sum为0的情况
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (mapSum.count(sum) > 0) {
                vecIndex.push_back(mapSum[sum] + 1);
                vecIndex.push_back(i);
                return vecIndex;
            }
            mapSum[sum] = i;
        }
        return vecIndex;
    }
};

2、最接近零的子数组和
https://www.lintcode.com/problem/subarray-sum-closest/description
描述
给定一个整数数组，找到一个和最接近于零的子数组。返回第一个和最右一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置

您在真实的面试中是否遇到过这个题？
样例
给出[-3, 1, 1, -3, 5]，返回[0, 2]，[1, 3]， [1, 1]， [2, 2] 或者 [0, 4]。

挑战
O(nlogn)的时间复杂度

分析：首先O(n^2)的算法很好想，直接枚举起点就行，看到挑战的复杂度，想肯定要排序或者二分什么的，这里没找出能二分的性质来，所以想只能想排序了，我们知道连续数组的和其实就是前缀和之间的差，而要求和最接近于零，也就是说，两个前缀和要最接近，那么直接前缀和排序，相邻两项比较即可

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    vector<int> subarraySumClosest(vector<int> &nums) {
        // write your code here
        vector<pair<int, int>> vecSum;
        int sum = 0;
        vecSum.push_back(make_pair(sum, -1));
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            vecSum.push_back(make_pair(sum, i));
        }
        sort(vecSum.begin(), vecSum.end());
        
        int minDiff = INT_MAX;
        int start, end;
        for (int i = 0; i < vecSum.size() - 1; i++) {
            if (abs(vecSum[i + 1].first - vecSum[i].first) <= minDiff) {
                minDiff = abs(vecSum[i + 1].first - vecSum[i].first);
                start = min(vecSum[i].second, vecSum[i + 1].second) + 1;
                end = max(vecSum[i].second, vecSum[i + 1].second);
            }
        }
        vector<int> vecIndex;
        vecIndex.push_back(start);
        vecIndex.push_back(end);
        return vecIndex;
    }
};