第83期-基础技巧：双指针 有序数组的平方

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

1 问题描述

给你一个按 非递减顺序 排序的整数数组 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]

初始代码

from typing import List
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        #在此之间填写代码

print(Solution().sortedSquares([-4,-1,0,3,10]))
print(Solution().sortedSquares([-7,-3,2,3,11]))

2 解题思路

• 标签：双指针
• 如果数组 nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；
• 如果数组 nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。
• 如果我们能够找到数组 nums 中负数与非负数的分界线，那么就可以用类似「归并排序」的方法了。
• 具体地，使用两个指针分别指向位置 neg 和 neg-1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。
• 当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。

3 解题方法

from typing import List
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        fd,a=0,len(nums)
        while fd<a:
            if nums[fd]>=0:
                break
            fd+=1
        fd,bk=fd,fd-1
        m=[]
        while fd<a or bk>-1:
            if fd==a or (fd<a and bk>-1 and nums[fd]>=-nums[bk]):
                m.append(nums[bk]**2)
                bk-=1
            else:
                m.append(nums[fd]**2)
                fd+=1
        return m

print(Solution().sortedSquares([-4,-1,0,3,10]))
print(Solution().sortedSquares([-7,-3,2,3,11]))

第1-3，20-21行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 定义前指针fd并赋值为0，同时定义变量a并复制列表的长度
第5-8行： 找出列表中第一个大于等于0的元素并将其索引赋值给fd，若没找到，则遍历到最后
第9行： 定义前指针、后指针分别为fd、bk，并赋值为fd和fd-1
第10行： 定义空列表m用于存放排列后的结果
第11行： 当前指针小于列表长度或者后指针大于等于0时执行循环
第12行： 若前指针等于列表长度或前后指针符合题意且前指针对应列表值大于后指针时
第13-14行： 在列表值添加后指针对应的数值的平方并将后指针向后移
第15-17行： 其他情况下，在列表值添加前指针对应的数值的平方并将前指针向前移
第18行： 返回最后排序后的列表

代码运行结果为：

算法讲解

这里用到了基础技巧：双指针，简单讲解下这个技巧：
什么是双指针（对撞指针、快慢指针）
双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

用法
对撞指针
对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

对撞数组适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题。

快慢指针
快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。

4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码