题目：997.有序数组的平方
997.有序数组的平方——力扣
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序
思考历程与知识点：
题目的意思很简单，就是把每个数的平方，按从小到大的顺序排个序，再输出出来。
第一想法是先每个数平方一遍，用sort（）函数排序一步到位。但是这道题用sort时间复杂度很高，主要考查的是对双指针的理解，所以两种方法都做一遍吧。
为什么选用双指针做法：因为原来的数组是有序的，并且可以有负数，所以平方之后最大值要么在最左边，要么在最右边，在左右两端放两个指针，依次比较排序，就可以得到排好的数组啦
题解：
1、用 sort() 一步到位法：
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { vector<int> res; for(int i : nums) res.push_back(i * i); sort(res.begin(),res.end()); return res; } }; 2、双指针法 class Solution { public: vector<int> sortedSquares(vector<int>& nums) { vector<int> res; int l = 0, r = nums.size()-1; while(r >= l){ if(nums[l] * nums[l] >= nums[r] * nums[r]) { res.push_back(nums[l]*nums[l]); l++; } else { res.push_back(nums[r]*nums[r]); r--; } } reverse(res.begin(),res.end()); return res; } };
其他语言版本：
java: class Solution { public int[] sortedSquares(int[] nums) { int right = nums.length - 1; int left = 0; int[] result = new int[nums.length]; int index = result.length - 1; while (left <= right) { if (nums[left] * nums[left] > nums[right] * nums[right]) { // 正数的相对位置是不变的， 需要调整的是负数平方后的相对位置 result[index--] = nums[left] * nums[left]; ++left; } else { result[index--] = nums[right] * nums[right]; --right; } } return result; } } python: class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: l, r, i = 0, len(nums)-1, len(nums)-1 res = [float('inf')] * len(nums) # 需要提前定义列表，存放结果 while l <= r: if nums[l] ** 2 < nums[r] ** 2: # 左右边界进行对比，找出最大值 res[i] = nums[r] ** 2 r -= 1 # 右指针往左移动 else: res[i] = nums[l] ** 2 l += 1 # 左指针往右移动 i -= 1 # 存放结果的指针需要往前平移一位 return res
题目：209. 长度最小的子数组
Leetcode原题链接：力扣
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组
[4,3]
是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
思考历程与知识点：
题目最后一句的进阶，相当于是提示有O（n）的解法，也有O（n log(n)）的解法。
但是，O（n）复杂度是小的那个，进阶反而要设计一个复杂度更大的，一般都应该反着来的，复杂度越小越好啊。所以题目是想引导我们思考别的解题方式。
那就先想想O（n）。第一反应，前缀和。想了想，确实就是O（n）的解法。
至于O（n log(n)），其实是滑动窗口，就像一只毛毛虫，从这个长长的数组上爬过去，身子下面的数字和如果小了，那其他位置不动，就头往前探探，多加几个数字，如果大了，那尾巴就收回来一点，少加几个数字。根据这个原则，毛毛虫爬完一趟，就知道最短的区间长度是多少了。（奇妙の比喻hhh）
题解：
class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int l = 0, r = 0,sum = nums[0]; int len = INT_MAX; while( 1) { if(sum < s && r+1 < nums.size()) { r++; sum=sum + nums[r]; } else if(sum >= s) { if(len > r - l + 1)len = r - l + 1; sum=sum - nums[l++]; } else{ break; } } if(len == INT_MAX)len = 0; return len; } };
其他语言版本：
java: class Solution { // 滑动窗口 public int minSubArrayLen(int s, int[] nums) { int left = 0; int sum = 0; int result = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) { sum += nums[right]; while (sum >= s) { result = Math.min(result, right - left + 1); sum -= nums[left++]; } } return result == Integer.MAX_VALUE ? 0 : result; } } python: class Solution: def minSubArrayLen(self, s: int, nums: List[int]) -> int: l = len(nums) left = 0 right = 0 min_len = float('inf') cur_sum = 0 #当前的累加值 while right < l: cur_sum += nums[right] while cur_sum >= s: # 当前累加值大于目标值 min_len = min(min_len, right - left + 1) cur_sum -= nums[left] left += 1 right += 1 return min_len if min_len != float('inf') else 0
题目：59.螺旋矩阵 II
Leetcode原题链接：59. 螺旋矩阵 II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
1 <= n <= 20
思考历程与知识点：
看起来是个模拟题，一圈一圈的模拟。那就按数字顺序，从左上角1开始一圈圈遍历。
比较复杂，可以看下官方的动画图解：59.螺旋矩阵II题解——力扣
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>> ans(n, vector<int>(n, 0)); int row = 0, col = 0; for(int i = 1; i <= n * n;){ //先向右，行不变，列+1 while(col < n && ans[row][col] == 0 && i <= n * n){ ans[row][col++] = i++; } row++; col--; //向下，列不变，行+1 while(row < n && ans[row][col] == 0 && i <= n * n){ ans[row++][col] = i++; } row--; col--; //向左，行不变，列-1 while(col >= 0 && ans[row][col] == 0 && i <= n * n){ ans[row][col--] = i++; } row--; col++; //向上，列不变，行-1 while(row >= 0 && ans[row][col] == 0 && i <= n * n){ ans[row--][col] = i++; } row++; col++; } return ans; } };
其他语言版本：
java: class Solution { public int[][] generateMatrix(int n) { int loop = 0; // 控制循环次数 int[][] res = new int[n][n]; int start = 0; // 每次循环的开始点(start, start) int count = 1; // 定义填充数字 int i, j; while (loop++ < n / 2) { // 判断边界后，loop从1开始 // 模拟上侧从左到右 for (j = start; j < n - loop; j++) { res[start][j] = count++; } // 模拟右侧从上到下 for (i = start; i < n - loop; i++) { res[i][j] = count++; } // 模拟下侧从右到左 for (; j >= loop; j--) { res[i][j] = count++; } // 模拟左侧从下到上 for (; i >= loop; i--) { res[i][j] = count++; } start++; } if (n % 2 == 1) { res[start][start] = count; } return res; } } python: class Solution: def generateMatrix(self, n: int) -> List[List[int]]: nums = [[0] * n for _ in range(n)] startx, starty = 0, 0 # 起始点 loop, mid = n // 2, n // 2 # 迭代次数、n为奇数时，矩阵的中心点 count = 1 # 计数 for offset in range(1, loop + 1) : # 每循环一层偏移量加1，偏移量从1开始 for i in range(starty, n - offset) : # 从左至右，左闭右开 nums[startx][i] = count count += 1 for i in range(startx, n - offset) : # 从上至下 nums[i][n - offset] = count count += 1 for i in range(n - offset, starty, -1) : # 从右至左 nums[n - offset][i] = count count += 1 for i in range(n - offset, startx, -1) : # 从下至上 nums[i][starty] = count count += 1 startx += 1 # 更新起始点 starty += 1 if n % 2 != 0 : # n为奇数时，填充中心点 nums[mid][mid] = count return nums
