一、数组理论回顾数组是存放在连续内存空间存放相同类型数据的集合可以通过下标快速取数据。重点数组元素不能真正删除只能用别的值把原来的元素覆盖掉。Python 列表与 numpy 数组小知识Python 普通列表存的是对象引用指针不是数据本身。修改列表元素只是改变引用指向的对象地址。NumPy 数组C 语言实现内存是连续的适合大量数值计算普通列表适合通用场景。二、有序数组的平方题目输入非递减排序的整数数组把每个数字平方输出依旧非递减排序的新数组。 示例输入[-4,-1,0,3,10]输出[0,1,9,16,100]方法 1暴力解法思路全部求平方再调用排序。代码简单但是排序会消耗额外时间。def sortedSquares(nums):squared_nums [x * x for x in nums]squared_nums.sort()return squared_nums方法 2双指针法原理负数平方之后会变大所以数组最大的平方值只会出现在数组最左边或者最右边。左指针l放在数组开头右指针r放在数组末尾结果数组从后往前填数。比较左右两边元素平方把更大的那个放到结果数组的末尾移动对应指针。循环直到左右指针相遇。class Solution:def sortedSquares(self, nums):l, r, i 0, len(nums)-1, len(nums)-1res [0] * len(nums)while l r:if nums[l] **2 nums[r]**2:res[i] nums[r]**2r -1else:res[i] nums[l]**2l 1i -1return res三、长度最小的子数组题目给正整数数组和目标值s找连续子数组子数组元素之和≥s求满足条件的子数组最小长度找不到返回 0。 示例s7nums[2,3,1,2,4,3]输出2子数组[4,3]。方法 1暴力双重循环外层循环定起始位置内层循环不断累加往后找一旦总和大于等于目标记录长度跳出内层循环。 缺点数据量大的时候运行很慢。class Solution:def minSubArrayLen(self, s, nums):l len(nums)min_len float(inf)for i in range(l):cur_sum 0for j in range(i, l):cur_sum nums[j]if cur_sum s:min_len min(min_len, j - i 1)breakreturn min_len if min_len ! float(inf) else 0方法 2滑动窗口用left、right两个指针代表窗口左右边界。right不断向右移动把数字加到总和cur_sum。当总和≥目标值就不断移动左边界left缩小窗口更新最小长度同时把滑出去的元素从总和减掉。right走到数组末尾结束。class Solution:def minSubArrayLen(self, s, nums):l len(nums)left 0min_len float(inf)cur_sum 0right 0while right l:cur_sum nums[right]while cur_sum s:min_len min(min_len, right - left 1)cur_sum - nums[left]left 1right 1return min_len if min_len ! float(inf) else 0