二分查找的注意点

思路：每次取list的最大最小下标，然后找到中间下标与其所对应的值，将其与目标比较大小，从而进一步缩短目标所在区间，时间复杂度logn

临界值的把握最重要

首先确定while循环的条件所在区间 如果我们假设了left <= right，那么就存在left == right这种情况，也就是target 可能位于left==right之间。 这个时候为了避免死循环，那么就需要在比完大小后right = middle-1 或者 left = middle+1，而不是直接left = middle 或right = middle 假设 nums = [2, 5]，target = 5： left = 0, right = 1 middle = (0 + 1) / 2 = 0（因为 / 是浮点数除法，应该用 // 取整） nums[middle] = nums[0] = 2 < target 执行 left = middle，但 middle == left，所以 left 没有变化 死循环（left 不增加，while left < right 不能终止）

如果假设了while循环条件是left < right的话，那就不需要考虑left==right了，这样就有right = middle而不是right = middle-1

27. Remove Element

第一种：暴力求解

1
2
3
4
5
6
i = 0 
while i < len(nums): 
    if nums[i] == val: 
        nums.pop(i) # 删除元素 
    else: i += 1 # 只有不删除时才递增索引 
return len(nums)

暴力求解，使用list.pop()删除元素，复杂度n^2，最简单，从头遍历，遍历到要删除的元素就删除，不是要删除的元素的话下标+1，最后返回删除完毕后的list

第二种：双指针方法

使用一个下标变量k从0开始记录新的数组（慢指针），使用另一个下标变量i记录遍历原数组（快指针） 

1
2
3
4
5
6
k = 0 
for i in range(len(nums)): 
if nums[i] != val: 
nums[k]=nums[i] 
k=k+1 
return k

只保留不等于val的元素，将其作为新的数组，由于第一个元素下标0的时候就进行判断，所以可以用同一个数组存放新的数组 最后得到的就是覆盖之后的

为什么 nums[k] = nums[i] 不会导致新数组 k 和原数组 i 混在一起？ 换句话说，为什么不会影响 nums[i] 后面的元素？

nums[k] = nums[i] 只会覆盖前面的部分，不会影响后面的部分 i 始终遍历原数组，它是从 0 → n-1 线性递增的。 k 仅递增存储有效元素的位置，它的值不会超过 i，它最多和 i 相等。 因此，每次 nums[k] = nums[i] 只会覆盖数组的前面部分，而 i 后面的元素仍然是原来的数据，不会影响后续遍历。

错误理解 正确理解 nums[k] = nums[i] 会破坏 nums[i] 后面的数据 nums[k] = nums[i] 只影响前面，不影响后面的遍历 nums[i] 被修改后，nums[i+1] 可能出错 nums[i] 仍然按顺序遍历，不会被提前覆盖 需要两层 for 处理 只需 O(n) 单层遍历

977. Squares of a Sorted Array

双指针处理平方和+升序排序问题

问题关键： 原序列不管是正数还是负数，都已经是升序排序好的，如[-4,-1,0,3,10] 因此在将所有数都平方后最大的数不是在最左边就是在最右边，中间的数一定不是最大的，所以我们只需要两两比较最左和最右边的数，得到的结果储存在新数组res里就完事，注意最后肯定会出现i=j的情况，此时有nums[i]** 2 == nums[j]** 2 ==同一个元素，因此将其直接存入res就行 在比大小完后需要将i和j分别指向下一个目标，同时k也应该往前更新位置

如果题目没说不能用新的list，那就可以创建新的list来储存排序的结果列表 res = [0]* len(nums) 注意 res=[]不行，空list不能调用索引k，所以报错 然后我们创建第一个指针指向新列表res的末尾 注意python 中用 i, j = 0, len(nums)-1 while i <= j: 来代替c++里的for(i=0, j=nums.size()-1, j<=j; ) 于是第二个指针指的是i j 两个分别指向nums的首尾元素

当然也可以先全部平方然后暴力排序秒杀O(n log n) nums.sort() sorted(nums)

209. Minimum Size Subarray Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
sum_, k, i = 0, 0, len(nums)-1

    nums.sort()
    while i >= 0:
        if nums[i] > target:
            return 1
        elif sum_ >= target:
            return k
        else:
            sum_ += nums[i]
            k += 1
        i -= 1
    return 0

这个方法不行，虽然通过了run，但是在submit的时候出错了

偶尔 能得到正确答案，但由于它 破坏了连续性要求，在某些情况下会 返回错误结果。最优解依然是 滑动窗口

滑动窗口也是双指针的一种，主要形容两个指针中间的序列

关键思想：首先想到暴力求解，也就是通过两个for循环，一个位于开头一个位于当前位置，i=0 j=i,这样可以算出所有的子序列并且找出最小的，复杂度最大为n^2

然后再想到通过一个for循环来解决问题，双指针！注意这个for循环只能指向子序列的终止位置，这样才能够”先动带后动“找到子序列，如果指向起始位置的话那么第二个指针还是得一遍一遍的遍历后面所有子序列，这样和暴力求解一样了。

然后先动带后动，第一个指针走前面，并且计算到跟前位置元素的和，直到和大于target才进行下一步操作，如果遍历结束都没有满足那就直接返回0.

大于target后就说明当前序列为止有子序列满足条件，但是不知道是否最短，所以我们先需要确定当前位置的子序列长度right-left+1，并且让其始终处于最短，然后通过while逐步从左减小sum的值并同时判断最小子序列是否满足大于target来缩小子序列长度。最后再挪动left指针，让其往前走一步。

感觉动手画一下会很清晰

59. Spiral Matrix II

问题的关键就是找到要旋转多少圈，每一圈的初始点在哪，每一边的开闭区间是否一致

其中可以观察到要旋转的圈数为n//2，这是因为每次往里面旋转横竖都得少两个元素，也就是外圈是nxn，第二圈是（n-2）x（n-2）

我们首先从左上角出发，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
i, j, count = 0, 0, 0
        offset = 1
        matrix = [[0] * n for _ in range(n)]
        while offset <= n//2:
            while j < n - offset:
                count += 1
                matrix[i][j] = count
                j += 1

            while i < n - offset:
                count += 1
                matrix[i][j] = count
                i += 1

            while j > 0:
                count += 1
                matrix[i][j] = count
                j -= 1

            while i > 0:
                count += 1
                matrix[i][j] = count
                i -= 1
            i += 1
            j += 1
            offset += 1

        if n%2 == 1:
            matrix[i][j] = n ** 2

        return matrix

这是错误的，首先原来我用的是浅拷贝matrix = [[0]* n ]* n，这样不会拷贝地址，所以错误，必须使用深拷贝matrix = [[0] * n for _ in range(n)]

第二个错误是 while j > 0和 while i > 0，这样可能导致跳出边界

现在gpt改的代码中将offset=0，并且在判断语句中使用j >= offset而不是j >0，因为如果有两圈以上的话第二层是在内层拐弯，而不是在最外层拐弯

while j >= offset确保遍历范围正确，不会漏掉最左侧列，matrix[i][j] == 0 防止重复填充，确保没填充的每一项都是0，避免错误覆盖

而 while i > offset 则是因为这一圈的第一个元素刚开始就被填充了旋转一圈后回到了起点的下面，因此不需要再填充，画个图会清晰明了。