209.长度最小的子数组
题目
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路
暴力解法主要就是两个for循环，一个for循环固定一个数组元素，例如n,另一个for循环从n的下一个元素开始累加，当和大于等于target时终止内层循环，并记录该最小长度。
滑动窗口（其实可以看成队列）主要就是通过不断地调节子序列的起始位置和终止位置来得到相应的结果。
我们把数组中的元素不停的入队，直到总和大于等于 s 为止，接着记录下队列中元素的个数，然后再不停的出队，直到队列中元素的和小于 s 为止（如果不小于 s，也要记录下队列中元素的个数，这个个数其实就是不小于 s 的连续子数组长度，我们要记录最小的即可）。接着再把数组中的元素添加到队列中……重复上面的操作，直到数组中的元素全部使用完为止。
解法
暴力解法
代码示例：
class Solution { public int minSubArrayLen(int target, int[] nums) { int result = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; if (sum >= target) { result = Math.min(result, j - i + 1); break; } } } return result == Integer.MAX_VALUE ? 0 : result; } }
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
队列相加法（滑动窗口）
代码示例
class Solution { public int minSubArrayLen(int target, int[] nums) { int result = Integer.MAX_VALUE; int startIndex=0; int endIndex=0; int sum = 0; for (endIndex=0; endIndex < nums.length; endIndex++) { sum+=nums[endIndex]; while (sum>=target) { result=Math.min(result,endIndex-startIndex+1); sum-=nums[startIndex]; startIndex++; } } return result == Integer.MAX_VALUE ? 0 : result; } }
- 时间复杂度：O(n)
- 空间复杂度：O(1)
对列相减法（滑动窗口）
代码示例
class Solution { public int minSubArrayLen(int target, int[] nums) { int result = Integer.MAX_VALUE; int startIndex=0; int endIndex=0; int sum = 0; for (endIndex=0; endIndex < nums.length; endIndex++) { target-=nums[endIndex]; while (target<=0) { result=Math.min(result,endIndex-startIndex+1); target+=nums[startIndex]; startIndex++; } } return result == Integer.MAX_VALUE ? 0 : result; } }
- 时间复杂度：O(n)
- 空间复杂度：O(1)
59.螺旋矩阵 II
题目
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
思路
顺时针螺旋排列的正方形矩阵的分析过程：
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去。
按照左闭右开的原则，画出相应的图。
解法
代码示例
class Solution { public int[][] generateMatrix(int n) { int startX = 0; int startY = 0; int[][] nums = new int[n][n]; int mid = n / 2;// 如果n为奇数，那么最中间的位置为mid，例如 n 为3，中间的位置下标为【1,1】 int m = 0;// 控制循环次数，每循环一圈加一 int offset = 1;// 每循环一圈，右边界收缩一位 int count = 1; int i, j; while (m++ < mid) { for (j = startY; j < n - offset; j++) { nums[startX][j] = count++; } for (i = startX; i < n - offset; i++) { nums[i][j] = count++; } for (; j > startY; j--) { nums[i][j] = count++; } for (; i > startX; i--) { nums[i][j] = count++; } startX++; startY++; offset++; } if (n % 2 != 0) { nums[mid][mid] = count; } return nums; } }
- 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
- 空间复杂度 O(1)
