企业官网建设流程全解析

上一篇文章把数组基础、二分查找和移除元素过了一遍，从数据结构的概念到具体代码实现，总算是把数组这块的基础打牢了。今天继续往下推进，课程进入数组算法进阶部分，主要讲了两道经典题目，有序数组的平方和长度最小的子数组，对应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代码实现起来比较简洁，但理解清楚边界条件和指针移动的时机才是关键。后续继续刷题的话，这两类技巧肯定还会不断遇到。希望这篇文章能给正在练习数组算法的同学一些参考，有问题欢迎来交流。