977.有序数组的平方

暴力求解(O(n+logn))

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(i**2 for i in nums)

双指针（O(n)）

由于列表是单调递增的，元素平方后的最大值要么在最前面，要么在最后面

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l, r = 0, len(nums) - 1
        res = [float('inf')]*len(nums)
        i = len(nums) - 1    # 从列表最后面开始赋值
        while l <= r:
            if nums[l]**2 < nums[r]**2: # 比较左右指针指向的值，谁最大就选谁赋值
                res[i] = nums[r]**2
                r -= 1
            else:
                res[i] = nums[l]**2
                l += 1
            i -= 1
        return res

209.长度最小的子数组

暴力解法

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        min_len = float('inf')
        for i in range(n):
            sum_val = 0
            for j in range(i, n):
                sum_val += nums[j]
                if sum_val >= target:
                    sub_len = j-i+1
                    min_len = min(min_len, sub_len)
                    break
        return min_len if min_len != float('inf') else 0

滑动窗口

什么时候缩小窗口

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        s, e = 0, 0
        min_len = float('inf')
        sum_val = 0
        while e < n:
            sum_val += nums[e]
            while sum_val >= target: # 缩小窗口, 这里 为什么不为 if ，因为开始指针向右移动一个位后，还有可能 sum_val >= target
                min_len = min(min_len, e-s+1)
                sum_val -= nums[s]
                s += 1
            e += 1
        return min_len if min_len != float('inf') else 0