长度最小的子数组

题目：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 >= s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

暴力法：使用双层for循环确定区间位置。外层循环遍历数组，为子区间起始位置，内层用于寻找满足要求的子区间的结束位置。当满足区间长度小于给定正整数时，跳出内层循环，暂存当前循环的最短子数组。

滑动窗口（本质是双指针）：
– 使用一层循环遍历数组并且用循环变量（右指针）表示区间的终点，另一个（左）指针用于动态更新区间的起点。
– 首先向左扩展区间，直到符合条件（本题中是区间和大于等于给定数值）。
– 符合基础条件后，通过移动右指针获取最优解（本题中是寻找最短的子数组），每次移动前记录新的最优解（如果有）。
– 当触发边界条件（区间和小于等于给定数值）时，本次循环结束，继续扩展区间。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        minL=len(nums)+1
        sum=0
        i=0 # 左端指针(为什么放在循环外？)
        # 先向右端扩大区间，再从左端缩小区间。
        for j in range(len(nums)):# 右端指针
            sum+=nums[j]
            while(sum>=target):
                # 更新区间长度
                l = j-i+1
                if l < minL:
                    minL=l
                # 缩小子区间,更新区间和与左指针
                sum-=nums[i]
                i+=1 

        return 0 if (minL==len(nums)+1) else minL

滑动窗口是一种用于处理连续子数组或子区间问题的高效算法，通过维护一个动态的窗口范围，避免重复计算，使时间复杂度降低到线性或接近线性。它的关键在于双指针的动态调整。

滑动窗口的应用场景：
滑动窗口主要用于处理需要在数组或字符串中查找连续区间的最大值、最小值、特定和等问题。例如：

子数组问题：

• 求和问题：找到和大于等于某个值的最小子数组。
• 固定长度问题：找固定长度子数组的最大和。

子字符串问题：

• 字符串中无重复字符的最长子串。
• 找到包含所有指定字符的最小子串。

双指针扩展问题：

• 检查是否存在符合条件的区间。
• 最小覆盖子串问题。

螺旋矩阵

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

转圈法

每画四条边就相当于转一圈，总共转n/2圈。模拟从左到右，从上到下，从右到左，从下到上的遍历填充过程，每次遍历固定遍历n-1个元素（左闭右开的遍历）。使用两个变量控制xy方向的起始位置。

设startx=0,starty=0,loop=0,offset=1,while循环的条件为loop <= n/2。在遍历过程中，通过offset遍历控制每一条边只遍历n-1个元素。注意当n为奇数的时候，需要特殊处理中心处的元素。
每次循环后，需要更新xy的起始位置和offset。（缩小边界）

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        startx,starty=0,0 #每次转圈的起始端点
        num,offset=1,1 #每次填入的数字，偏移量用于控制每条边遍历n-1个元素
        mid=n//2 #矩阵中心位置
        loop=0 #循环计数
        nums = [[0]*n for _ in range(n)] # 创建二维数组
        while(loop<=n/2): #转n/2圈
            # 遍历的原则：每条边遍历n-1个元素
            # 从左到右
            for i in range(starty,n-offset):
                nums[startx][i]=num
                num+=1
            # 从上到下，列是n-offset
            for j in range(startx,n-offset):
                nums[j][n-offset]=num
                num+=1
            # 从右到左，行是n-offset
            for i in range(n-offset,starty,-1):
                nums[n-offset][i]=num
                num+=1
            # 从下到上
            for j in range(n-offset,startx,-1):
                nums[j][starty]=num
                num+=1
            startx+=1
            starty+=1
            offset+=1
            loop+=1
        # n为奇数的时候，矩阵中心需要特殊处理
        if(n%2!=0):
            nums[mid][mid]=num
        return nums

四边界法

同样模拟从左到右，从上到下，从右到左，从下到上的遍历填充过程。
用上下左右四个边界变量控制需要填充的边界，使用while循环决定是否继续填充。每条边填充元素的数量不是固定的。
设 left=0,right=n-1,top=0,botton=n-1。while的条件为(left <= right) and (top <= botton)，或者直接num<=n*n

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
         left,right = 0,n-1 # 四个边界变量，值为初始边界位置的索引
         top,botton = 0,n-1
         num=1 # 填充的数字
         matrix=[[0]*n for _ in range(n)] # 生成二维数组
         while (left<=right) and (top<=botton):#注意区间边界条件
            # 从左到右，注意边界为right+1
            # (python range左闭右开，所以需要加一访问到最后一个元素)
            for i in range(left,right+1):
                matrix[top][i]=num
                num+=1
            # 上边界缩小
            top+=1
            # 从上到下
            for i in range(top,botton+1):
                matrix[i][right]=num
                num+=1
            #右边界缩小
            right-=1
            # 从右到左,逆序遍历，注意边界为left-1
            for i in range(right,left-1,-1):
                matrix[botton][i]=num
                num+=1
            # 下边界缩小
            botton-=1
            # 从下到上,逆序遍历，注意边界为top-1
            for i in range(botton,top-1,-1):
                matrix[i][left]=num
                num+=1
            # 左边界缩小
            left+=1

         return matrix

区间和

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

输入示例

5
1
2
3
4
5
0 1
1 3

输出示例

3
9

数据范围：

0 < n <= 100000

假设查询m次，如果每次查询都遍历一次数组相关的区间，复杂度是O(m*n)。使用前缀和的思想降低复杂度：计算数组每个位置的累加，放入一个累加结果数组中。查询时直接使用累加结果数组对应区间元素之差即可算出原数组的区间和。例如想要计算区间[left,right]的元素和，计算累加结果数组presum[right]-presum[left-1]即可

import sys
input = sys.stdin.read

def main():
    data = input().split() # 以空格为分隔符，分隔所有数据。返回一个字符串列表。
    index = 0
    n = int(data[index]) #注意input获取的输入是字符串，运算前需要强转类型
    index+=1
    presums=[]
    presum=0
    for i in range(n):
        presum+= int(data[i+1])
        presums.append(presum)
    index+=n

    while(index<len(data)): #通过索引长度可以判断输入何时停止
        l,r = int(data[index]),int(data[index+1])
        index+=2

        if l==0:
            print(presums[r])
        else:
            print(presums[r]-presums[l-1])


main()