这是第二次刷代码随想录的算法训练营，距离上次30期训练营过去整整一年，一年中在实习以及HKUST学到了很多，这次为明年春秋招做准备，加油。

 704. 二分查找

在CIST5500课程的分治章节也是刚学一遍，写代码的话无论是左闭右开左闭右闭主要注意循环不变式的定义（这里以左闭右开为例）：

这里断言：如果target在nums中，则在每一轮循环target一定在[left, right)中。

写代码注意保持循环不变式，就不会产生边界错误。因为首先循环条件一定针对如果target不在nums中，则[left,right)是一个空数组，那么只需要left>=right就停；其次针对左闭右开区间，在比较完nums[mid]和target的大小后，在赋值阶段为了保持循环不变式，需要查剩下的所有部分，那剩下的部分如何确定呢，对于上一轮的[left, right)， 如果现在查左半边，mid开始都查过了，那就把开区间移动到mid处即可，查右半边，把闭区间移动到mid+1即可。

左闭右闭也是同理。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)

        while left < right:
            mid = (right - left) // 2 + left
            
            if nums[mid] > target:
                right = mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                return mid

        return -1

27. 移除元素

双指针初见，快指针去访问所有元素，慢指针经过的位置就是符合要求的数组。

这里我理解其实和后面DP的滚动数组有点像。

题目中限制是in-place操作，假如没有这个限制，我会想新开一个数组，然后遍历nums，把不等于val的entry都扔到新数组里面。这里造成了内存的浪费，因为把slow指针指向原数组相比指向新数组是没有损失的。复用空间，完成了in-place删除。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

977.有序数组的平方

我理解这是双指针的另一种形式吧，头尾双指针相向而行，有一点像归并排序的归并操作。因为平方的性质，平方最大的只能在数组头尾产生，则头尾双指针指向的较大的先放进数组，然后反向填充。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left, right = 0, n - 1
        res = [0] * n
        pos = n - 1
        while left <= right:
            if abs(nums[left]) >= abs(nums[right]):
                res[pos] = nums[left] ** 2
                pos -= 1
                left += 1
            else:
                res[pos] = nums[right] ** 2
                pos -= 1
                right -= 1
        return res