# Evolve from brute force to optimal

1. O(n^3), compute the sum of all sub arrays.
``````    int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size(), len = n+1;
for(int i=0;i<n;i++)
for(int j=i;j<n;j++) {
int sum = 0;
for(int k=i;k<=j;k++) sum+=nums[k];
if(sum>=s) {
len = min(len,j-i+1);
break;
}
}
return len==n+1? 0:len;
}
``````
1. O(n^2), compute the sum of a sub array can be improved to constant by computing prefix sum.
``````    int minSubArrayLen(int s, vector<int>& nums) {
int n = nums.size(), len = n+1;
vector<int> pre(n);
for(int i=1;i<n;i++) pre[i]=pre[i-1]+nums[i-1];
for(int i=0;i<n;i++)
for(int j=i;j<n;j++) {
int sum = pre[j]-pre[i]+nums[j];
if(sum>=s) {
len = min(len,j-i+1);
break;
}
}
return len==n+1? 0:len;
}
``````
1. O(nlogn) The prefix sum array is increasing so we can do binary search.
``````    int minSubArrayLen(int s, vector<int>& nums) {
if(nums.empty()) return 0;
int n = nums.size(), len = n+1;
vector<int> pre(n);
pre[0]=nums[0];
for(int i=1;i<n;i++) pre[i]=pre[i-1]+nums[i];
for(auto i = pre.begin(); i!=pre.end();i++) {
auto j = lower_bound(i,pre.end(),*i+s-nums[i-pre.begin()]);
if(j!= pre.end()) len = min(len,int(j-i)+1);
}
return len==n+1? 0:len;
}
``````
1. O(n) Two pointers.
``````    int minSubArrayLen(int s, vector<int>& nums) {
int l=0,r=0, sum=0, n = nums.size(), len=n+1;
while(r < n) {
sum+=nums[r++];
if(sum<s) continue;
while(sum>=s) sum-=nums[l++];
len = min(len, r-l+1);
}
return len == n+1 ? 0:len;
}
``````

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