lintcode:Subarray Sum Closest

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].

Challenge
O(nlogn) time

这题个人感觉比较难；
思路：
1.求数组每一项的前缀和（包括该项）；
2.对前缀和排序；
3.求差的绝对值最小的两个相邻前缀和项；

1.提交1

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
        int len=nums.size();
        vector<int> res(2);

        if(len==1){
           res[0]=0;
           res[1]=0; 
           return res;
        }

        vector<int> sums(len);

        sums[0]=nums[0];
        for(int i=1;i<len;i++){
            sums[i]=sums[i-1]+nums[i];

        }

       vector<int> new_sums=sums;

        sort(new_sums.begin(),new_sums.end());

        int min=INT_MAX;
       // int min_id;
        int index1,index2;
        for(int i=1;i<len;i++){
            int diff=abs(new_sums[i]-new_sums[i-1]);
            if(diff<min){
                min=diff;
                //min_id=i;
                for(int j=0;j<len;j++){
                  if(sums[j]==new_sums[i-1]){
                    index1=j;
                  }
                  if(sums[j]==new_sums[i]){
                    index2=j;
                  }
                }
                if(index2<index1){
                    swap(index1,index2);
                }
                index1++;
            }
        }

        //int index1,index2;


        res[0]=index1;
        res[1]=index2;

        return res;
    }
};

大部分数据测试试正确的，单有少部分不行。个人觉得原因是有前缀和相同的项。

所以本题还有一个难点，就是既要求前缀和，又要保存其相应的索引。

用map不行，可以使用pair，而且对pair我还有一个以前忽略的地方，含pair对象的vector可以直接排序，如

#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
using namespace std;

int main(){
    vector<pair<int, int> >vec;
    vec.push_back({3,1});
    vec.push_back({2,2});
    vec.push_back({1,3});

    sort(vec.begin(),vec.end());

    for (int i = 0; i < vec.size();i++){
        cout << vec[i].first<<" "<<vec[i].second<<endl;
    }


    return 0;
}

也就是对pair的first进行从小到大的排序。

AC代码：

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
        int len=nums.size();
        vector<int> res(2);

        if(len==1){
            res[0]=0;
            res[1]=0;
            return res;
        }

        vector<pair<int,int> > sums_index(len);

        sums_index[0]={nums[0],0};
        for(int i=1;i<len;i++){
            sums_index[i].first=sums_index[i-1].first+nums[i];
            sums_index[i].second=i;
        }

        sort(sums_index.begin(),sums_index.end());

        int min_diff=INT_MAX;
        int left,right;
        for(int i=1;i<len;i++){
            int diff=abs(sums_index[i].first-sums_index[i-1].first);
            if(diff<min_diff){
                min_diff=diff;
                left=min(sums_index[i].second,sums_index[i-1].second)+1;
                right=max(sums_index[i].second,sums_index[i-1].second);
            }
        }


        res[0]=left;
        res[1]=right;
        return res;
    }
};