My code:
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int length = Integer.MAX_VALUE;
int sum = 0;
int head = 0;
int tail = 0;
while (head < nums.length) {
if (tail > nums.length)
break;
if (sum >= s) {
if (length > tail - head)
length = tail - head;
sum -= nums[head];
head++;
}
else {
if (tail == nums.length)
break;
else
sum += nums[tail++];
}
}
if (length == Integer.MAX_VALUE)
return 0;
else
return length;
}
public static void main(String args[]) {
Solution test = new Solution();
int[] a = {1, 1};
System.out.println(test.minSubArrayLen(3, a));
}
}
My test result:
这次作业比较简单吧。类似于移动窗口，当找到了最大值后，此时对于head来说，length最小。然后，将头部从sum中减去。再判断，此时sum是否>= s， 如果否，则继续移动tail。如果是，则继续移动head。 这样，不断地刷新最小length，同时遍历了数组。
到了康村了。美国人真的都很热情，或者说，伊萨卡的人都很友善。感觉练口语的机会比英国多很多，自己也不是特别怕讲英文了。
然后，这里真的好村。。。什么都没有。今天把卧室收拾好了，舍友很安静，然后这边除了美女多，其他真的没什么诱惑。希望不要在研究生搞什么出轨之类的分神。
继续说，现在的环境很安静，恩，我下定决心了，在这块土地，闭关学习一年半，一定要成大器！
LDN的工作特别忙，让我怎么再忍心去催她托福的事。比如今天是她这周唯一一天休息。虽然昨天她答应了要八点起床奋斗，而现在没起。但这不是很正常嘛？忙了一周了，难得一天，睡到中午休息下，你让我怎么忍心去骂她。换了我也扛不住啊。
希望，她可以顺利吧。
**
总结： two pointer, sliding window
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] sum = new int[n];
int temp = 0;
for (int i = 0; i < n; i++) {
temp += nums[i];
sum[i] = temp;
}
int begin = 0;
int end = 0;
int c = 0;
int min = Integer.MAX_VALUE;
while (end < n) {
c += nums[end];
if (c < s) {
end++;
}
else {
min = Math.min(min, end - begin + 1);
c -= nums[end];
c -= nums[begin];
begin++;
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}
就是累加数组 + 滑动窗口
下面介绍另外一种做法。
My code:
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] sums = new int[n];
int temp = 0;
for (int i = 0; i < n; i++) {
temp += nums[i];
sums[i] = temp;
}
int index = ceil(sums, s);
if (index == -1) {
return 0;
}
int min = Integer.MAX_VALUE;
for (int i = index; i < nums.length; i++) {
int leftMargin = floor(0, i - 1, sums[i] - s, sums);
min = Math.min(min, i - leftMargin);
}
return min == Integer.MAX_VALUE ? 0 : min;
}
private int ceil(int[] nums, int target) {
if (target > nums[nums.length - 1]) {
return -1;
}
int begin = 0;
int end = nums.length - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] > target) {
end = mid - 1;
}
else if (nums[mid] < target) {
begin = mid + 1;
}
else {
return mid;
}
}
return begin;
}
private int floor(int i, int j, int target, int[] nums) {
if (target < nums[i]) {
return -1;
}
int begin = i;
int end = j;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] > target) {
end = mid - 1;
}
else if (nums[mid] < target) {
begin = mid + 1;
}
else {
return mid;
}
}
return end;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = new int[]{1,4,4};
int ret = test.minSubArrayLen(4, nums);
System.out.println(ret);
}
}
同样是累加数组。先找到 >= s 的最小值的index
从他开始往右遍历，每次遍历，都找到 [0, i - 1]范围内，小于等于
s - sum[i] 的最大值的index
然后不断更新最小长度。
就做出来了。
下面介绍两个子问题。
给定一个 nums[]. target, 求 该数组中，大于等于target的最小值的index
private int ceil(int[] nums, int target) {
int begin = 0;
int end = nums.length - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] > target) {
end = mid - 1;
}
else if (nums[mid] < target) {
begin = mid + 1;
}
else {
return mid;
}
}
return begin;
}
求小于等于target 的最大数的index
private int floor(int[] nums, int target) {
int begin = 0;
int end = nums.length - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] > target) {
end = mid - 1;
}
else if (nums[mid] < target) {
begin = mid + 1;
}
else {
return mid;
}
}
return end;
}
感觉会经常用，记住了。
Anyway, Good luck, Richardo! -- 09/21/2016
