还是用双指针解决问题，不过这次用双指针形成个滑动窗口

看来数组问题用双指针解决还挺常见

209. 长度最小的子数组

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

给定一个含有 n 个正整数的数组和一个正整数 target 。

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

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：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)) 时间复杂度的解法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 子数组需要连续
        # 使用双指针，slow指针用于删除元素，fast指针用来添加元素；若添加后的元素让总sumOfnums大于等于target，则可以进行pop（删除），并保持删除后的sum仍大于等于target

        # sumOfnums = sum(nums)
        slow = 0
        L = len(nums)
        res = float('inf')

        # if sumOfnums < target:
        #     return 0

        newSum = 0

        # 循环pop
        for fast in range(L):
            newSum += nums[fast]

            while newSum >= target:
                res = min(res, fast - slow + 1) 
                newSum -= nums[slow]
                slow += 1
                # newSum在减掉nums[slow]后，不一定会再大于target，不需要再将res-1
                # res -= 1
        
        # 通过让res与inf比较，从而得知是否存在长度最小的子数组满足条件，否则就返回0；
        # 这样的好处是不需要对整个数组求和
        if res != float('inf'):
            return res
        return 0

59. 螺旋矩阵 II

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

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

示例 1：

img

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

示例 2：

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

提示：

  • 1 <= n <= 20

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # 一个大循环
        # 包含四个for循环

        loop, mid = n//2, n//2   #迭代次数，n为奇数时，矩阵的中心点
        index = 1
        startx, starty = 0, 0
        nums = [[0] * n for _ in range(n)]
        for offset in range(1, loop + 1):
            # 第一行
            for i in range(starty, n - offset):
                nums[startx][i] = index
                index += 1
            # 最后一列
            for j in range(startx, n - offset):
                nums[j][n - offset] = index
                index += 1
            # 最后一行
            for i in range(n - offset, starty, -1):
                nums[n - offset][i] = index 
                index += 1
            # 第一列
            for j in range(n - offset, startx, -1):
                nums[j][starty] = index
                index += 1
            startx += 1
            starty += 1
        
        if n % 2 != 0:
            nums[mid][mid] = index
        return nums

58.区间和（第九期模拟笔试）

题目描述

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

输入描述

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

输出描述

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

输入示例

1
2
3
4
5
6
7
8
5
1
2
3
4
5
0 1
1 3

输出示例

1
2
3
9

提示信息

数据范围：
0 < n <= 100000

代码

  • 时间复杂度O(N)
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import sys
def main():
    data = sys.stdin.read().split()
    Ld = len(data)
    n = int(data[0])

    data = list(map(int, data))
    nums = list()
    sumOfnums = [0] * (n + 1)
    
    for i in range(1, n + 1):
        num = data[i]
        nums.append(num)
    
    # print(nums)
    sumOfnums[1] = nums[0]
    for i in range(1, n):
        sumOfnums[i + 1] = sumOfnums[i] + nums[i]
    
    # print(sumOfnums)
    i = n + 1
    while i < Ld:
        # print(i, i+ 1)
        a, b = data[i], data[i + 1]
        print(sumOfnums[b - n] - sumOfnums[a - n - 1])
        i += 2
        
if __name__ == "__main__":
    main()

技巧

使用 data = sys.stdin.read().split() , 一次性将所有输入读取进来

44.开发商购买土地（第五期模拟笔试）

题目描述

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

输入描述

第一行输入两个正整数，代表 n 和 m。

接下来的 n 行，每行输出 m 个正整数。

输出描述

请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

输入示例
1
2
3
4
3 3
1 2 3
2 1 3
1 2 3
输出示例
1
0
提示信息

如果将区域按照如下方式划分：

1 2 | 3
2 1 | 3
1 2 | 3

两个子区域内土地总价值之间的最小差距可以达到 0。

数据范围：

1 <= n, m <= 100；
n 和 m 不同时为 1。

思路

看到本题，大家如果想暴力求解，应该是 n^3 的时间复杂度，

一个 for 枚举分割线， 嵌套 两个for 去累加区间里的和。

如果本题要求 任何两个行（或者列）之间的数值总和，大家在0058.区间和 的基础上 应该知道怎么求。

就是前缀和的思路，先统计好，前n行的和 q[n]，如果要求矩阵 a行 到 b行 之间的总和，那么就 q[b] - q[a - 1]就好。

至于为什么是 a - 1，大家去看 0058.区间和 的分析，使用 前缀和 要注意 区间左右边的开闭情况。

本题也可以使用 前缀和的思路来求解，先将 行方向，和 列方向的和求出来，这样可以方便知道 划分的两个区间的和。

代码

  • 时间复杂度O(N2)
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def main():
    n, m = map(int, input().split())

    grid = list()
    sumOfGrid = 0
    for _ in range(n):
        line = list(map(int, input().split()))
        sumOfGrid += sum(line)
        grid.append(line)

    sumV = [0] * m
    sumH = [0] * n

    for i in range(n):
        sumH[i] = sum(grid[i])
    
    for j in range(m):
        for i in range(n):
            sumV[j] += grid[i][j]
    
    # print(sumH, sumV)

    res = float('inf')
    temp = 0
    for i in range(n):
        temp += sumH[i]
        res = min(res, abs(sumOfGrid - temp - temp))
    
    temp -= temp
    for j in range(m):
        temp += sumV[j]
        res = min(res, abs(sumOfGrid - temp - temp))
    
    print(res)

if __name__ == "__main__":
    main()