209. 长度最小的子数组

leetcode链接：
https://leetcode.cn/problems/minimum-size-subarray-sum/description/

暴力求解

方法一：

public int minSubArrayLen(int target, int[] nums) {

	// 方案一： 暴力求解

	int left=0,
			right=-1,
			result = nums.length,
			flag = 0;

	for (int i = 0; i < nums.length; i++) {
		right++;
		if (sum(left, right, nums, target)) {
			for (int j = left; j <= right; j++) {
				left++;
				if (!sum(left, right, nums, target) && j != right) {
					left--;
					flag = right - left + 1;
					if (flag < result) {
						result = flag;
					}
					break;
				} else if (j == right ) {
					if (nums[j] >= target) {
						return 1;
					}
				}
			}
		}
	}
	if (flag == 0) {
		return 0;
	}
	return result;
}

public boolean sum(int left, int right, int[] nums, int target) {
	int sumAll = 0;
	for (int i = left; i <= right; i++) {
		sumAll += nums[i];
	}

	if (sumAll >= target) {
		return true;
	}
	return false;
}

结果

时间超时

方法二

基于方案一的优化

暴力求解修改—-求和修改

int left=0,
right=-1,
result = nums.length,
flag = 0,
sum = 0;

for (int i = 0; i < nums.length; i++) {
	sum += nums[++right];
	if (sum >= target) {
		for (int j = left; j <= right; j++) {
			sum -= nums[left++];

			if (sum < target && j != right) {
				flag = right - left + 2;
				if (flag < result) {
					result = flag;
				}
				break;
			} else if (j == right ) {
				if (nums[j] >= target) {
					return 1;
				}
			}

		}
	}
}
if (flag == 0) {
	return 0;
}
return result;

结果

• 20/20 cases passed (1 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 77.58 % of java submissions (48.6 MB)

官方方案

参考链接：

https://leetcode.cn/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= s) {
                    ans = Math.min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

时间复杂度：O( n² )
空间复杂度：O( 1 )

前缀和 + 二分查找

参考链接： 答案中的方法二

https://leetcode.cn/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/

二分查找的前提：数组是通过升序或者降序进行排列的
此题目将数组中的内容相加，需要注意：最后一位的数据不能溢出。

本回答中直接使用了java中自带的二分搜索方法，此方法相关介绍：
Arrays.binarySearch 详解

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1]; 
        // 为了方便计算，令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

滑动窗口–较优方案

官方答案

参考链接： 答案中的方法三
https://leetcode.cn/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析

• 时间复杂度：O( n )， 其中 n 是数组的长度。指针 startstart 和 endend 最多各移动 n 次。
• 空间复杂度：O( 1 )

自己编写

引进、消化、吸收、创新

int result = 0,
		sum = 0,
		left = 0,
		right = 0,
		nums_length = nums.length;
for (right = 0; right < nums_length; right++) {
	sum += nums[right];
	if (sum >= target) {
		if (result > (right - left + 1) || result == 0) {
			result = right - left + 1;
		}
		for ( ; left <= right; left++) {
			sum -= nums[left];
			if (sum < target) {
				left++;
				break;
			}

			if (result > (right - left)) {
				result = right - left;
			}
		}
	}

}

return result;

结果

• 20/20 cases passed (1 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 69.66 % of java submissions (48.7 MB)