首页 > itarticle > pg

pg

admin 11月 13, 2020 0

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;
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能