139. 最接近零的子数组和

139. 最接近零的子数组和 中文 English

给定一个整数数组，找到一个和最接近于零的子数组。返回第一个和最右一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置 样例

样例1

输入: [-3,1,1,-3,5] 输出: [0,2] 解释: [0,2], [1,3], [1,1], [2,2], [0,4]

挑战

O(nlogn)的时间复杂度 注意事项

数据保证任意数的和都在[−231,231−1][-2^{31},2^{31}-1][−2​31​​,2​31​​−1]范围内

vector<int> subarraySumClosest(vector<int> &nums) {

    int first = -1;     int second = -1;     int sum = 0;     int min = INT_MAX;     vector<int> ret;

    vector<pair<int, int>> sumPairVec;     sumPairVec.push_back(pair<int, int>(0,0));     vector<int> sumVec;

    for (int i = 0; i<nums.size(); i++)     {         if (nums[i] == 0)         {             ret.push_back(nums[i]);             ret.push_back(nums[i]);             return ret;         }         sum =  sum + nums[i];         sumPairVec.push_back(pair<int, int>(sum, i+1));         sumVec.push_back(sum);     }

    sort(sumVec.begin(),sumVec.end());//和排序     vector<int> minVec;     for (int i = 1; i < sumVec.size(); i++)//找和的差最小两个数     {         if (sumVec[i-1] == 0)         {             first = sumVec[i-1];             second = 0;             min = 0;             break;         }

        if (sumVec[i] - sumVec[i - 1] < min)         {             first = sumVec[i-1];             second = sumVec[i];             min = sumVec[i] - sumVec[i - 1];         }     }          if (first != -1)     {         for (int i = 1; i < sumPairVec.size(); i++)         {             if (sumPairVec[i].first == first)             {                 first = sumPairVec[i].second;                 break;             }         }

        for (int i = 1; i < sumPairVec.size(); i++)         {             if (sumPairVec[i].first == second && first != sumPairVec[i].second)             {                 second = sumPairVec[i].second;                 break;             }         }

        int start = std::min(first, second);         int end = std::max(first, second) -1;

        if (min == 0)         {             ret.push_back(start);             ret.push_back(end);             return ret;         }         ret.push_back(start);         ret.push_back(end);

    }     if (ret.empty())     {         return{ 0,0 };     }

    return ret;

}

void test() {     //vector<int> nums = { -3,1,1,-3,5};     //vector<int> nums = { 3, -3, 5 };     //vector<int> nums = { 5, 10, 5, 3, 2, 1, 1, -2, -4, 3 };     vector<int> nums = { -4, 5, -4, 5, -4, 5, -4, 5, -4, 5, -4, 5, -4, 5, -4, 5, -4, 5, -1000 };     //vector<int> nums = { 4, 10, 13, 4, -1, 0, 3, 3, 5 };

    vector<int> ret = subarraySumClosest(nums); }