# JAVA two pointer solution 1ms O(n),O(1) and divide and conquer solution 3ms O(nlogn), O(1)

• ``````   /**
* two pointers solution with o(1) space complexity;
*/
public static int minSubArrayLen(int s, int[] nums) {
int min = 0;
int left = -1;
int sum = 0;
for (int i = 0, j = 0; j < nums.length; j++) {
if (left == -1) {
sum += nums[j];
if (sum >= s) {
left = sum - s;
while (left - nums[i] >= 0) {
left -= nums[i ++];
if (i == j) return 1;
}
min =  j - i + 1;
}
}else {
left = nums[j] + left;
while (left - nums[i] >= 0) {
left -= nums[i ++];
if (i == j) return 1;
}
min = Math.min(min, j - i + 1);
}
}
if (left == -1) return 0;
return min;
}
``````

the divide and conquer:

`````` /**
* divide and conquer n*log(n);
*/
public int minSubArrayLen(int s, int[] nums) {
if (nums.length == 0) return 0;
int res = findMin(s, 0, nums.length-1, nums);
return res == Integer.MAX_VALUE? 0:res;
}

private int findMin(int tag, int left, int right, int[] nums) {
if (left == right) {
return Integer.MAX_VALUE;
}

int mid = (left + right)/2;

//divide :
int l = findMin(tag, left, mid, nums);
int r = findMin(tag, mid + 1, right, nums);

//conquer:
return Math.min(findmiddle(left, right, mid, nums, tag),Math.min(l, r));
}
/**
* find the minSize which must contains nums[m] ;
*/
private int findmiddle(int l, int r, int m, int[] nums, int tag) {
if (nums[m] >= tag) return 1;
int min = Integer.MAX_VALUE;
int left = -1;
int sum = nums[m];
int i = m - 1;
for (; i >= l; i --) {
sum += nums[i];
if (sum >= tag) break;
}
if (sum >= tag) {
min = m - i + 1;
left = sum - tag;
}
else i = l;
for (int j = m + 1; j <= r && i <= m; j++) {
if (left == -1) {
sum += nums[j];
if (sum >= tag) {
left = sum - tag;
while (left - nums[i] >= 0) {
left -= nums[i ++];
if (i == m ) return j - i + 1;
}
min =  j - i + 1;
}
}else {
left = nums[j] + left;
while (left - nums[i] >= 0) {
left -= nums[i ++];
if (i == m) return Math.min(min, j - i + 1);
}
min = Math.min(min, j - i + 1);
}
}
if (left == -1) return Integer.MAX_VALUE;
return min;
}
``````

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