pg

Given an unsorted array of integers, find a subarray which adds to a given number. If there are more than one subarrays with the sum as the given number, print any of them.

Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {10, 2, -2, -20, 10}, sum = -10
Ouptut: Sum found between indexes 0 to 3

Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20
Ouptut: No subarray with given sum exists


Numbers are positive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<pair<int, int>> subArraySum(vector<int> nums, int sum){
vector<pair<int, int>> res;
int i = 0, j = 0;
int cursum = 0;
while(j < nums.size()){
cursum += nums[j++];
while(cursum >= sum && i <= j-1){
if(cursum == sum)
res.push_back(make_pair(i, j-1));
cursum -= nums[i++];
}
}
return res;
}

Numbers are negative.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<pair<int, int>> neSubArraySum(vector<int> nums, int sum){
vector<pair<int, int>> res;
int cursum = 0;
unordered_map<int, int> preSum;
for(int i = 0; i < nums.size(); i++){
cursum += nums[i];
if(cursum == sum){
res.push_back(make_pair(0, i));
}
if(preSum.find(cursum - sum) != preSum.end()){
res.push_back(make_pair(preSum[cursum-sum] + 1, i));
}
preSum[cursum] = i;
}

return res;
}