上一篇文章把数组基础、二分查找和移除元素过了一遍从数据结构的概念到具体代码实现总算是把数组这块的基础打牢了。今天继续往下推进课程进入数组算法进阶部分主要讲了两道经典题目有序数组的平方和长度最小的子数组对应LeetCode上的977题和209题。这两道题的核心解法都涉及到了双指针和滑动窗口这两个在算法题中非常高频的技巧。先回顾一下数组的基础理论。数组是存放在连续内存空间上的相同类型数据的集合数组可以通过下标索引的方式快速获取对应的数据。这里有个很重要的特性需要注意数组的元素是不能删除的只能覆盖。这个特性在移除元素那道题里体现得很明显所谓的删除其实是用后面的元素覆盖前面的元素。在Python中列表实际上存储的是对象的引用而不是对象本身每个元素都是一个指向实际对象的指针。当修改列表中的元素时比如把my_list[0]从1改成100实际上是把索引0指向了整数对象100而不是修改了整数对象1本身因为整数是不可变对象。NumPy数组则不一样它是用C语言实现的存储在连续的内存块中专为数值计算设计效率比Python列表高不少。选择哪种数据结构取决于应用场景需要高效数值计算时选NumPy需要通用灵活的数据结构时选Python列表。有序数组的平方这道题的题目描述是给你一个按非递减顺序排序的整数数组nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。比如nums [-4, -1, 0, 3, 10]平方后是[16, 1, 0, 9, 100]排序后是[0, 1, 9, 16, 100]。最直观的暴力解题思路是先计算每个元素的平方然后对整个数组排序。用列表推导式squared_nums [x * x for x in nums]一行就能算出平方然后调用sort方法排序。这个方法的时间复杂度取决于排序算法Python的Timsort是O(n log n)空间复杂度O(n)。对于这道题来说暴力解法虽然能过但不是最优的。双指针法才是这道题的精髓所在。关键在于输入数组本身就是有序的负数平方后可能变得很大但数组两端的平方值一定是最大的。比如[-4, -1, 0, 3, 10]平方后最大的是100在最右边次大的是16在最左边。所以可以用两个指针分别指向数组的左右两端比较两个指针对应元素的平方值把较大的那个放到新数组的最右侧。具体做法是定义left 0指向数组开头right len(nums) - 1指向数组末尾再定义一个result数组和一个指针pos从len(nums)-1开始往前填充。比较nums[left]的平方和nums[right]的平方如果左边的平方大就把它放到result[pos]然后left加1往右移如果右边的平方大就把它放到result[pos]然后right减1往左移。这样一趟遍历下来时间复杂度O(n)比暴力解法的O(n log n)快了不少。这道题完美展示了双指针技巧在数组问题中的应用。长度最小的子数组这道题是另一个经典问题给定一个含有n个正整数的数组和一个正整数s找出该数组中满足其和大于等于s的长度最小的连续子数组并返回其长度。如果不存在符合条件的子数组返回0。示例s 7, nums [2, 3, 1, 2, 4, 3]输出是2因为子数组[4, 3]的和是7长度是2。暴力解法是用两层循环枚举所有子数组外层循环确定起始位置内层循环从起始位置开始累加一旦和大于等于s就更新最小长度并跳出内层循环。这个方法时间复杂度O(n²)在数组长度较大的时候会超时题目提示nums.length可以达到10^5暴力解法肯定不行。滑动窗口法是这道题的最优解法时间复杂度O(n)。滑动窗口的本质是两个指针维护一个区间根据条件动态调整窗口的大小。具体做法是定义left和right两个指针都从0开始用一个变量current_sum记录窗口内元素的和用min_len记录满足条件的最小子数组长度。right指针不断向右移动把nums[right]加入窗口current_sum增加。当current_sum大于等于s时说明当前窗口满足条件更新min_len然后尝试缩小窗口把nums[left]从窗口中移除left右移直到current_sum小于s为止。这样每个元素最多被加入窗口一次、移出窗口一次时间复杂度O(n)。这道题用到的滑动窗口思想在处理子数组、子字符串问题时非常常见维护一个动态区间根据条件移动左右边界是解决连续区间问题的利器。把今天这两道题和前一篇的二分查找、移除元素放在一起看数组相关的算法虽然基础但变化非常丰富。双指针和滑动窗口这两种技巧在各种数组题目中反复出现掌握了它们就能解决相当一部分数组类的算法题。Python代码实现起来比较简洁但理解清楚边界条件和指针移动的时机才是关键。后续继续刷题的话这两类技巧肯定还会不断遇到。希望这篇文章能给正在练习数组算法的同学一些参考有问题欢迎来交流。