代码随想录算法训练营第二天| 977—有序数组的平方、209—长度最小的子数组

977-有序数组的平方

• 直接平方存在原数字是负数的情况，所以平方操作的顺序会变。这个时候简单的思路是先依次做平方操作，然后再sort，但是这样子没有利用上原本数组的有序性。
• 第二个思路就是利用上原数组的有序性，设置两个指针指向原数组头和尾，此时左指针和右指针必有一方是绝对值最大（也即平方操作后最大）的数字，可以被放在平方后数组的最后一位。
• 在放置该数字后左（或右）指针往中间移动，依次从绝对值的大到小把数字从后往前放到结果数组里即可。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left,right,i = 0,len(nums)-1,len(nums)-1
        res = [float('inf')] * len(nums)
        while left <= right:
            left_val = nums[left]**2
            right_val = nums[right]**2
            if left_val < right_val:
                res[i] = right_val
                right -= 1
            else:
                res[i] = left_val
                left += 1
            i -= 1
        return res

209-长度最小子数组

• 第一反应是收集窗口长度为1的子数组、为2的、...、为长度n的，但是这样子时间复杂度太高了，看代码随想录说内存也会爆掉
• 使用滑动窗口的方法，用两层循环保证两件事情，就可以把时间复杂度降低到O(2n)，也即O(n)：
  1. 外层循环：
     负责窗口右边缘，也即右指针向右推进。每次推进一位
  2. 内存循环：
     负责窗口左指针，也即左指针向左推进。
     在窗口内数字之和>target的情况下不断推进左指针直到获取当前右边缘下的min_len为止
• 这里最棒的剪枝在于，在当前窗口长度为x的情况下，右指针向前推进一位之后并不会排列检索窗口长度>=x+1的情况，因此把时间复杂度降到了O(2n)

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_l,l = 0,len(nums)
        left,right = 0,0
        min_len = float('inf')
        cur_sum = 0  # 当前累加值

        while right < l:
            cur_sum += nums[right]

            while cur_sum >= target:
                min_len = min(min_len,right-left+1)
                cur_sum -= nums[left]
                left += 1
            right += 1
        return min_len if min_len!=float('inf') else 0