-
Notifications
You must be signed in to change notification settings - Fork 22
/
139.subarray-sum-closest.cpp
43 lines (37 loc) · 1.25 KB
/
139.subarray-sum-closest.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct cmp
{
bool operator()(pair<int, int>&a, pair<int, int>&b)
{
return a.first < b.first;
}
};
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>> prefix_sum;
prefix_sum.push_back(make_pair(0, -1));
for(auto i = 0; i < nums.size(); ++i)
{
int sum = nums[i] + prefix_sum[prefix_sum.size() - 1].first;
prefix_sum.push_back(make_pair(sum, i));
}
sort(prefix_sum.begin(), prefix_sum.end(), cmp());
int closest = INT_MAX;
vector<int> ans(2, 0);
for (auto i = 1; i < prefix_sum.size(); ++i)
{
if (abs(prefix_sum[i].first - prefix_sum[i - 1].first) < closest)
{
closest = abs(prefix_sum[i].first - prefix_sum[i - 1].first);
ans[0] = min(prefix_sum[i].second, prefix_sum[i - 1].second) + 1;
ans[1] = max(prefix_sum[i].second, prefix_sum[i - 1].second);
}
}
return ans;
}
};