Leetcode-Array-ques/MinSizeSubArrSum.cpp at master · coder-Utkarsh/Leetcode-Array-ques · GitHub

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<iostream>
#include<climits>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
// todo: Given an array of positive integers nums and a positive integer target, return
// the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of
// which the sum is greater than or equal to target. If there is no such subarray,
// return 0 instead.
int minSubArrayLen(int target, vector<int>& nums)
{
    int sum;
    int p = nums.size()-1;
    int q;

    while (nums[p]>target)
    {
        // if(nums[p]==target)
        //     return 1;
        p--;
        if(p<0)
            return 0;
    }

    if(p==0)
        return 1;

    q=p-1;
    sum = nums[p];
    for(int i=p; i>=0; i--)
    {
        if(sum==target)
            return p-q;
        else if(sum > target)
            break;

        sum += nums[q];
        q--;
    }

    for(int i=q+1; p!=q; i++)
    {
        if(sum==target)
            return p-q;

        sum -= nums[p];
        p--;
    }
    return 0;
}
int minSubArrayLen2(int target, vector<int> nums)
{
    int p = 0, q = 1, sum;
    int size = nums.size();
    priority_queue <int, vector<int>, greater<int>> h;

    if(nums[p] == target || nums[q] == target)
        return 1;

    h.push(INT_MAX);
    cout << "dbug in\n";
    sum = nums[p]+nums[q];
    while (p < size && q < size)
    {
        if(sum > target)
        {
            sum -= nums[p];
            p++;
        }
    // cout << "dbug\n";
        else if(sum < target)
        {
            q++;
            if(q<size)
                sum += nums[q];
            // else
                // p++;
        }
    // cout << "dbug\n";
        else
        {
            if (q==p)
                return 1;
            else if (q-p < h.top())
                h.push(q-p+1);

            sum -= nums[p];
            p++;
            q++;
            if(q<size)
                sum += nums[q];
            // else
                // p++;
        }
        cout << "\np = " << p << " q = " << q;
    // cout << "dbug\n";
    }
    while (p < size)
    {
        cout << "\n@2nd loop";
        if(sum==target)
            h.push(q-p);
        sum -= nums[p];
        p++;
    }

    cout << "dbug out\n";

    if(h.top()==INT_MAX)
        return 0;
    return h.top();
}
int main()
{
    int target, x;
    vector<int> v;

    cin >> target;

    for(int i=0; i<9; i++)
    {
        cin >> x;
        v.push_back(x);
    }
    target = minSubArrayLen2(target, v);

    cout << endl << "ans = " << target;
}