LeetCodeCampsDay2数组part02

同样需要使用快/慢指针/双指针，另外，可以使用前缀和数组、二分查找

209. 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

问题

给定一个含有 n 个正整数的数组和一个正整数 target
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

核心思路

外循环：使用for循环，被遍历对象为快指针(right)，通过 ⁠right 指针扩展窗口
内循环：当窗口和(the sum of windows) >= ⁠target 时，记录当前窗口长度，并尝试收缩(shrink)窗口以找到更小的子数组
跳出条件：如果数组为空或没有符合的子数组，⁠min_length 保持为最大值float(‘inf’)时，最终返回 0

代码

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        currentSum = 0
        left = 0
        L = len(nums)
        # Set the minimumWindows as a positive inf
        minimumWindows = float('inf')
        for right in range(L):
          	# keep add nums to currentSum
            currentSum += nums[right]
            # if currentSum is bigger than target,
            # try to shrink the minimumWindows from the left to find a smaller currentSum.
            while currentSum >= target and left <= right:
              	# shrink the windows
                minimumWindows = min(minimumWindows, right - left + 1)
                # remove the leftmost elements from the sum
                currentSum -= nums[left]
                left += 1
        
        return 0 if minimumWindows == float('inf') else minimumWindows

O(nlogn)时间复杂度的解法

这个解法使用前缀和数组(prefix array)结合二分查找：

先计算前缀和数组，prefix[i] 表示 nums[0] 到 nums[i-1] 的和

对于每个右端点 j（对应子数组结束位置），使用二分查找找到第一个子数组和 >= target 的最大右端点。

时间复杂度：O(n log n)，因为计算前缀和是 O(n)，每个右端点进行一次二分查找是 O(log n)，总共 O(n log n)

空间复杂度：O(n)，用于存储前缀和数组

思路

使用前缀和数组来快速计算子数组的总和
我们需要找到一个子区间nums[j…k]，而且sum(nums[j…k]) >= target；而sum(nums[j…k]) = ⁠prefix[k+1] - prefix[j]，于是就有prefix[k+1] - prefix[j] >= target, 于是就有prefix[k+1] >= target + prefix[j]
使用（变体）二分搜索在前缀和数组中（从prefix[j…k])，找到第一个大于target + prefix[j]的下标mid，从而计算最小长度

代码

L = len(nums)
prefix = [0] * (L + 1)
# prefix[1] = nums[0], prefix[2] = nums[1], etc.
for i in range(1, L + 1):
    prefix[i] = prefix[i - 1] + nums[i - 1]

if prefix[L] < target:
    return 0
print(prefix)
minimumWindows = float('inf')

for j in range(0, L + 1):
    # The need is to find a ⁠nums[j..k] which >= target，the sum of nums[j..k] = ⁠prefix[k+1] - prefix[j]
    # Which means `⁠prefix[k+1] - prefix[j] >= target`, noted by `⁠prefix[k+1] >= prefix[j] + target`
    # Hence, ⁠value = prefix[j] + target is the lowest boundary that satisfied the need
    # value = prefix[j] + target # we can set this result to 'value' to reduce the repeated calculation.
    if prefix[j] + target > prefix[L]:
        break
    # Find the first value which >= value by using binary search
    left, right = j, L
    while left != right:
      	# 
        mid = (left + right) // 2
        if prefix[mid] >= prefix[j] + target:
            right = mid
        else:
            left = mid + 1
    # right(or left) is the first index which >= ⁠value in prefix
    # where the right equals to the lowest 'k+1' making the sum of nums[j..k] >= target
    minimumWindows = min(minimumWindows, right - j)
return minimumWindows

59. 螺旋矩阵 II

https://leetcode.cn/problems/spiral-matrix-ii/

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 20

思路

这题目不考算法，但考编程能力；

这题目有个关键点是，弄清楚赋值的规律：将上、右、下、左四条边依次赋值，并且每次赋值时，都遵循“左开右闭”原则

比如第一行1->2->3，仅赋值1和2），而第二条（3->4->5），仅赋值(3->4);第三条(5->6->7)，仅赋值(5->6)；最后一条(7->8->1)，同样仅赋值(7->8)

这样完成了一个“回”字形赋值

代码

下面代码可以优化成仅用一个offset，因为startX/startY与offset变化方式是一致的

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
      	# startX是指纵向下标
        startX = 0
        # startY是指横向下标
        startY = 0
        # offset用来计算开区间
        offset = 1
        # 左闭右开
        nums = [[1 for _ in range(n)] for _ in range(n)]

        count = 1 
        for _ in range(n//2):
            for j in range(startY, n - offset):
                nums[startX][j] = count
                count += 1
                # print(nums)
            for i in range(startX, n - offset):
                nums[i][n - offset] = count
                count += 1
                # print(nums)
            for j in range(n - offset, startY - 1, -1):
                nums[n - offset][j] = count
                count += 1
                # print(nums)
            for i in range(n - offset - 1, startX , -1):
                nums[i][j] = count
                count += 1
                # print(nums)
            startX += 1
            startY += 1
            offset += 1
        
        if n % 2 == 1:
            nums[n//2][n//2] = count
        return nums

209. 长度最小的子数组

问题

核心思路

代码

O(nlogn)时间复杂度的解法

思路

代码

59. 螺旋矩阵 II

思路

代码

相关推荐