数组2
Task
977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II ，总结
建议大家先独立做题，然后看视频讲解，然后看文章讲解，然后在重新做一遍题，把题目AC，最后整理成今日当天的博客
拓展题目可以先不做
977.有序数组的平方
题目建议： 本题关键在于理解双指针思想
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep
给你一个按 非递减顺序 排序的整数数组 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]
代码
//先找到大于0的点，再往两边拓宽
func sortedSquares(nums []int) []int {
i := 0
n := len(nums)
for ;i < n; i++{
if nums[i] > 0{
break
}
}// [0,i-1] [i,n-1]
ans := make([]int,0,n)
for l,r := i-1, i; l >= 0 || r < n; {
if l < 0 {
ans = append(ans,nums[r]*nums[r])
r++
}else if r >= n {
ans = append(ans,nums[l]*nums[l])
l--
}else if nums[l] * nums[l] > nums[r] * nums[r]{
ans = append(ans,nums[r] * nums[r])
r++
}else{
ans = append(ans,nums[l] * nums[l])
l--
}
}
return ans
}
//双指针，两边轮流加答案
func sortedSquares(nums []int) []int {
m := len(nums)
ans := make ([]int,m)
l := 0
r := m-1
idx := 0
for l <= r{
if(nums[l]*nums[l]>nums[r]*nums[r]){
ans[m-1-idx] = nums[l]*nums[l]
idx++
l++
}else{
ans[m-1-idx] = nums[r]*nums[r]
idx++
r--
}
}
return ans
}
//first half get smallest number and then two direction
209.长度最小的子数组
题目建议： 本题关键在于理解滑动窗口，这个滑动窗口看文字讲解 还挺难理解的，建议大家先看视频讲解。 拓展题目可以先不做。
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE
给定一个含有 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
代码
//left and right two pointers and if less than target extend right,if larger than and len longer than extend left
func minSubArrayLen(target int, nums []int) int {
//l and r two pointer , move r until >=target,then update len,then move l until < target
m := len(nums)
l := 0
r := 0
tempval := 0
ans := math.MaxInt32
for r < m {
for r < m && tempval < target {
tempval += nums[r]
r++
}// get most right
for l < m && tempval >= target{
ans = min(r-l,ans)
tempval -= nums[l]
l++
}
}
if ans > m{
return 0
}else{
return ans
}
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
59.螺旋矩阵II
题目建议： 本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/
总结
题目建议：希望大家 也做一个自己 对数组专题的总结
文章链接：https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html
func generateMatrix(n int) [][]int {
t := 0
b := n-1
l := 0
r := n-1
idx := 1
mat := make([][]int,n)
for k := range mat {
mat[k] = make([]int,n)
}
for idx <= n*n {
for i := l; i <= r; i++{
mat[t][i] = idx
idx++
}
t++
for j := t; j <= b; j++{
mat[j][r] = idx
idx++
}
r--
for i := r; i >= l; i-- {
mat[b][i] = idx
idx++
}
b--
for j := b; j >= t; j-- {
mat[j][l] = idx
idx++
}
l++
}
return mat
}
