# C++ O(N) and O(NlogN), very very clear

• ``````class Solution {
public:
//O(NlogN)  binary search
int minSubArrayLen(int s, vector<int>& nums) {
if(nums.empty()){
return 0;
}
int size = nums.size();
vector<int> sum(size, 0);
sum[0] = nums[0];
for(int i = 1; i < size; ++i){
sum[i] = sum[i - 1] + nums[i];
}
int minlen = INT_MAX;
for(int i = 0; i < size; ++i){
int p = lower_bound(sum[i] + s - nums[i], i, size, sum);
if(p != size){
minlen = min(minlen, p - i + 1);
}else{
break;
}
}
return minlen == INT_MAX ? 0 : minlen;
}
int lower_bound(int x, int left, int right, vector<int>& sum){
while(left < right){
int mid = left + (right - left) / 2;
if(sum[mid] < x){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
/* O(N) two pointers
int minSubArrayLen(int s, vector<int>& nums) {
if(nums.empty()){
return 0;
}
int size = nums.size();
int i = 0,j = 0;
int sum = 0;
int minlen = INT_MAX;
while(j < size){
while(j < size && sum < s){
sum += nums[j];
++j;
}
if(sum < s){
break;
}
while(i < j && sum >= s){
sum -=nums[i];
++i;
}
minlen = min(minlen, j - i + 1);
}
return minlen == INT_MAX ? 0 : minlen;
}
*/
};
``````

by the way, the upper_bound is ( which is not related to this problem, I just share ):

``````int upper_bound(int x, int left, int right, vector<int>& sum){
while(left < right){
int mid = left + (right - left) / 2;
if(sum[mid] <= x){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.