977.有序数组的平方

链接 思路：双指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        length = len(nums)
        i, j = 0, length-1
        k = length - 1
        res = [-1] * length
        while i <= j:
            if nums[i] * nums[i] > nums[j] * nums[j]:
                res[k] = nums[i] * nums[i]
                i += 1
            else:
                res[k] = nums[j] * nums[j]
                j -= 1
            k -= 1
        
        return res

时间复杂度：O(n)

209.长度最小的子数组

链接 思路：滑动窗口。单次循环

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        ans = float("inf")
        total = 0
        i = 0 # 起始位置

        for j in range(len(nums)):
            total += nums[j]
            while total >= target:
                ans = min(ans, j - i + 1)
                total -= nums[i]
                i += 1

        if ans == float("inf"):
            return 0
        return ans

时间复杂度：O(n)

59.螺旋矩阵II

链接 思路：模拟法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        ans = float("inf")
        total = 0
        i = 0 # 起始位置

        for j in range(len(nums)):
            total += nums[j]
            while total >= target:
                ans = min(ans, j - i + 1)
                total -= nums[i]
                i += 1

        if ans == float("inf"):
            return 0
        return ans

时间复杂度：O(n2)

参考：

https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG