代码随想录算法训练营Day2

977, 有序数组的平方

给了提示双指针,一遍过芜湖,不多解释.

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:# 提示two pointers 双指针# Constraints: nums非空,inta,b = 0,len(nums) - 1res = []while a <= b:if abs(nums[a]) >= abs(nums[b]):res.append(nums[a] ** 2)a += 1elif abs(nums[a]) < abs(nums[b]):res.append(nums[b] ** 2)b -= 1return res[::-1]# TC:O(N)# SC:O(N)

209, 长度最小的子数组

for循环指针终止位置, while sum(nums[a:b]) >= target更新窗口起始位置的指针, a += 1.

第一遍O(N^2)超时,第二遍sum(nums[a:b])超时

sum(nums[a:b])超时解法

# 超时解法
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:if sum(nums) < target:return 0windowLen = len(nums)a = 0for b in range(1,len(nums)+1):  # for循环标记的是终止位置while sum(nums[a:b]) >= target:# print(a,b,nums[a:b])windowLen = min(b - a, windowLen)a += 1return windowLen用sum(nums[a:b])也会超时

正确解法

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:if sum(nums) < target:return 0windowLen = len(nums)a = 0sumL = 0for b in range(1,len(nums)+1):  # for循环标记的是终止位置sumL += nums[b-1]while sumL >= target:# print(a,b,nums[a:b])windowLen = min(b - a, windowLen)sumL -= nums[a]a += 1return windowLen# TC:O(N)# SC:O(1)

请问一下, 209.长度最小的子数组,使用滑动窗口,时间复杂度O(N)大概能想明白;best case是sum(nums) == target,只需要for循环求一次累加,时间复杂度还是O(N);那worst case是什么情况?

比较容易困惑的点在于“移动指针a的次数”，因为每次移动都需要比较sumL >= target,来决定是否要 pop， 所以很多人会认为worst case time complexity 是 O(kn)，其实不然。因为当你这一次pop了k个数以后，不会再对这k个数进行操作.

换一种角度看，因为push函数里的while循环里本质上是pop出不可能的candidate，而每个数只会被pop一次。

因此，从整个array的角度来看这个while的循环条件最多只会比较2n次（考虑到会有一次比较不成立所以多考虑一次），因此复杂度为O(n)。Example:比如数组里所有元素都是target,第一次sumL >= target成立并删除元素,第二次sumL >= target不成立进入下一个b的循环.这样是O(2N).

59, 螺旋矩阵II

不太会,再想想