数组02

代码问题

1. Python中逻辑与是and，而不是&，后者是位运算符
2. 列表切片中间不要用逗号

困惑

暂无

PLUS

对比以下两端代码：

点击查看代码1

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        flag = 0
        length_nums = len(nums)
        length_current = 1e5 + 1
        for left in range(length_nums):
            for right in range(left+1, length_nums+1):
                sum_current = sum(nums[left:right])
                length_tmp = len(nums[left:right])
                if sum_current >= target and length_tmp < length_current:
                    length_current = length_tmp
        if length_current != 1e5 + 1:
            return length_current
        else:
            return 0

点击查看代码2

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        min_length = 1e5+1
        left = 0  # 左指针
        current_sum = 0  # 当前窗口的和
        for right in range(n):
            current_sum += nums[right]  # 右指针右移，扩大窗口
            # 当当前和大于等于目标值时，尝试缩小左边界
            while current_sum >= target:
                # 计算当前窗口长度并更新最小值
                current_length = right - left + 1
                if current_length < min_length:
                    min_length = current_length
                # 左指针右移，缩小窗口
                current_sum -= nums[left]
                left += 1
        # 如果找到符合条件的子数组，返回最小长度，否则返回0
        return min_length if min_length != 1e5+1 else 0

前者是暴力枚举，时间复杂度是O(n²)；后者是滑动窗口，时间复杂度是O(n)。
后者之所以优于前者，是因为避免了很多不必要的子集的重复计算

来源链接：https://www.cnblogs.com/rachel3140/p/19027733