算法训练营day02 | {209.长度最小的子数组, 59.螺旋矩阵II, 3.区间和, 4.开发商买土地}

第一章数组-part02，知识点为双指针滑动窗口、模拟题、前缀和。

209. 长度最小的子数组

1.1 看到题目的想法

给定一个含有n个正整数的数组和一个正整数s，题目要求找出该数组中满足其和≥ s的长度最小的连续子数组，并返回其长度。一开始理解错了题意，以为是先排序再截取前几个元素即可，再读一遍题，其实是要求不能变动数组的相对位置，只想到了两层for循环，枚举出所有符合条件的子区间，记录最小长度。代码如下：

▶

暴力解法

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    ans = Math.min(ans, (j - i + 1));
                    break;
                }
            }
        }
        // 不存在符合条件的子数组返回0
        return Integer.MAX_VALUE == ans ? 0 : ans;
    }
}

1.2 看完代码随想录的想法

先看的视频讲解，还是双指针的思想，在一个for循环下完成两个for循环的工作，两个指针谁作为循环索引向后移动，需要考虑清楚这个问题。
- 只用一个for循环，那么这个循环的索引，一定是表示滑动窗口的终止位置。
- 滑动窗口的起始位置如何移动呢，明显地，当子数组的和超过s时就向后移动，但注意什么时候停止，当和小于s时停止，之间可能不止移动一次！

妙啊！精妙，时间复杂度降低为On，代码如下：

▶

滑动窗口

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int sum = 0, i = 0;  // 起始索引
        for (int j = 0; j < nums.length; j++) {  // 结束索引
            sum += nums[j];
            while (sum >= target) {
                ans = Math.min(ans, (j - i + 1));
                sum -= nums[i++];
            }
        }
        return Integer.MAX_VALUE == ans ? 0 : ans;
    }
}

59. 螺旋矩阵II

题目链接：59.螺旋矩阵II
文档讲解：代码随想录–59螺旋矩阵II
视频讲解：一入循环深似海 | LeetCode：59.螺旋矩阵II
状态：模拟题，第一遍自己写写画画，耗时很久还没解出题目。

2.1 看到题目的想法

没啥想法，Java打印一个二维数组的循环还咨询了一下GPT，代码如下：

▶

打印二维数组

public static void main(String[] args) {
        int n = 7;
        int[][] ans = GenerateMatrix.generateMatrix(n);
        for(int[] row : ans) {
            for(int val : row) {
                System.out.printf("%3d ", val);
            }
            System.out.println();
        }
    }

如果不用矩阵打印，调用Arrays.deepToString(ans)，能看到内部数据。
Teacher Shan提供了一种和题解不一样的思路，像贪吃蛇，定义上下左右4种方向，初始化二维数组，初始方向设为右，若下一步的位置超过矩阵边界或者方格已有数据，则顺时针旋转，进入下一个方向，妙啊。
- 停止条件：直至填入n*n个元素，计数停止。

▶

方位法

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int[][] POS = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 右下左上
        int MaxCount = n * n;
        int curNum = 1;
        int x = 0, y = 0;
        int posIndex = 0; // 初始方向设为右
        while(curNum <= MaxCount) {
            matrix[x][y] = curNum++;
            int newX = x + POS[posIndex][0], newY = y + POS[posIndex][1];
            if(newX < 0 || newX >= n || newY < 0 || newY >= n || matrix[newX][newY] != 0) {
                posIndex = (posIndex + 1) % 4;
            }
            x = x + POS[posIndex][0];
            y = y + POS[posIndex][1];
        }
        return matrix;
    }
}

2.2 看完代码随想录的想法

要写出正确的二分法一定要坚持循环不变量的原则；要模拟出本题依然要坚持循环不变量的原则。四条边每画一条都要坚持一致的左闭右开原则，看了视频讲解的思路后，写出了第一版代码：

▶

左闭右开不变量解法

public static int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];

        int circle = n / 2;
        int startX = 0, startY = 0;
        int offset = 1;  // 随着圈数不一样在收缩
        int count = 1;
        while(circle > 0) {
            circle--;
            int i = startX, j = startY;
            // 坚持左闭右开原则去处理
            for (; j < n - offset; j++) {
                ans[startX][j] = count++;
            }
            for (; i < n - offset; i++) {
                ans[i][j] = count++;
            }
            for (; j > startY; j--) {
                ans[i][j] = count++;
            }
            for(; i > startX; i--) {
                ans[i][j] = count++;
            }
            // 更新值
            startX++;
            startY++;
            offset++;
        }

        if (n % 2 == 1) {  // 奇数n单独处理，矩阵中心的一个点
            ans[n/2][n/2] = count;
        }
        return ans;
    }

3. 区间和

文档讲解：代码随想录–3. 区间和
状态：看了题目想了一会，没想到使用前缀和的算法思想。

3.1 解题过程

时间原因，看了题目之后继续看了文档题解，看完思路又打开了，前缀和的思想是重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数，在涉及计算区间和的问题时非常有用。
例如：要计算vec数组的下标2到下标5之间的累加和，用前缀和数组的p[5]-p[1]就可以了。

我的前缀和数组留了一个哨兵的位置，这样可以省略if判断，代码如下：

▶

一维数组前缀和

package cn.leetcode.again;

import java.util.Arrays;
import java.util.Scanner;

public class PrefixSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int[] pre = new int[n + 1];
        // 同时计算前缀和
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
            pre[i + 1] = pre[i] + arr[i];
        }

        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(pre));

        while(scanner.hasNextInt()) {
            int startIndex = scanner.nextInt();
            int endIndex = scanner.nextInt();
            int ans = pre[endIndex + 1] - pre[startIndex];
            System.out.println(ans);
        }
        scanner.close(); // 释放资源
    }
}

4. 开发商购买土地

文档讲解：代码随想录–4. 开发商购买土地
状态：没做出来。

4.1 解题过程

一开始不是很理解题目，一个n*m的土地区域，只能竖着隔开一刀，或者横着隔开一刀，需要求两个子区域内土地总价值之间的最小差距。
其实分别从x轴和y轴两个方向上来看，设置两个一维前缀和数组即可，一个子区域A首先通过前缀和的思想算出累加和，另一个子区域B等于S_total - S_A
并且原始的二维矩阵数组没必要保存下来，在输入的过程中已经可以计算两个方向上每行、每列的和。

随后退化为《第三题–区间和》。

▶

开发商购买土地

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] row = new int[n];  // 每一行的和
        int[] col = new int[m];
        int total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int val = scanner.nextInt();
                row[i] += val;
                col[j] += val;
                total += val;
            }
        }

        // 按照行分块，枚举数组下标
        int ans = Integer.MAX_VALUE;
        int prefix = 0;
        for (int i = 0; i < n - 1; i++) {
            prefix += row[i];
            ans = Math.min(ans, Math.abs(total - prefix * 2));  // 有没有可能是一个负数，有可能
        }

        // 按照列分块
        prefix = 0;
        for (int i = 0; i < m - 1; i++) {
            prefix += col[i];
            ans = Math.min(ans, Math.abs(total - prefix * 2));
        }
        System.out.println(ans);
    }
}

5. 今日收获

又理解了一点双指针的思想，一个for循环下完成两个for循环的工作，很妙啊。
前缀和的算法思想也很妙啊，关于区间求和的问题都可以考虑用这个思路解法维度，开阔了思路。
数组专题总结：4种典型的数组题目
- 二分法
- 双指针法
- 滑动窗口（也是一种双指针）
- 模拟行为
- 前缀和

Leetcode > 数组

#Java #代码随想录

算法训练营day02 | {209.长度最小的子数组, 59.螺旋矩阵II, 3.区间和, 4.开发商买土地}

http://paopaotangzu.xyz/cn/day02_leetcode/

作者

PROTON TANG

发布于

2025年12月18日

许可协议

算法训练营day03 | {203. 移除链表元素, 707.设计链表, 206.反转链表} 上一篇

算法训练营day04 | {24.两两交换链表中的节点, 19.删除链表的倒数第N个节点, 160. 链表相交，142. 环形链表II} 下一篇