代码随想录算法训练营第二天| 209.长度最小的子数组 59.螺旋矩阵II 区间和 开发商购买土地

209. 长度最小的子数组

题目：

给定一个包含正整数的数组 nums 和一个正整数 target ，找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 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 <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

进阶：

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

暴力解法：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = nums.length + 1;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum = sum + nums[j];
                if (sum >= target && result > j - i + 1) {
                    result = j - i + 1;
                }
            }
        }
        if (result == nums.length + 1) {
            return 0;
        } else {
            return result;
        }
    }
}

滑动窗口解法：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = nums.length + 1;
        int sum = 0;
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = sum + nums[i];
            while (sum >= target) {
                if (result > i - left + 1) {
                    result = i - left + 1;
                }
                sum = sum - nums[left];
                left++;
            }
        }
        if (result == nums.length + 1) {
            return 0;
        } else {
            return result;
        }
    }
}

解题思路：

滑动窗口是一种高效解决连续子数组问题的算法，特别适用于寻找满足特定条件的最小或最大子数组。该方法的核心思想是在遍历数组时维护一个窗口（即子数组），当窗口中的元素和满足目标条件时，缩小窗口的大小以尝试找到更小的子数组。

步骤：

1. 初始化两个指针 left 和 right，并使用一个变量 sum 来存储窗口内元素的和。
2. 当 right 指针向右扩展时，将 nums[right] 加入 sum，形成窗口。
3. 当窗口内的和大于等于目标 target 时，计算当前窗口长度，并尝试缩小窗口，直到窗口内的和小于 target。
4. 在每次窗口满足条件时更新最小子数组长度。

这种方法的时间复杂度为 O(n)，因为每个元素在遍历过程中最多只会被访问两次。

59. 螺旋矩阵 II

题目：

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

示例：

• 输入: n = 3
• 输出:

[
 [1, 2, 3],
 [8, 9, 4],
 [7, 6, 5]
]

代码：

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int startx = 0;
        int starty = 0;
        int loop = 1;
        int count = 1;
        int offset = 1;
        int i, j;

        while (loop <= n / 2) {
            for (j = starty; j < n - offset; j++) {
                result[startx][j] = count;
                count++;
            }
            for (i = startx; i < n - offset; i++) {
                result[i][n - offset] = count;
                count++;
            }
            for (j = n - offset; j > startx; j--) {
                result[n - offset][j] = count;
                count++;
            }
            for (i = n - offset; i > starty; i--) {
                result[i][starty] = count;
                count++;
            }
            startx++;
            starty++;
            offset++;
            loop++;
        }

        if (n % 2 == 1) {
            result[startx][starty] = count;
        }

        return result;
    }
}

解题思路：

螺旋矩阵是一个典型的二维数组遍历问题，要求我们按照顺时针的顺序填充一个 n x n 的正方形矩阵。可以通过分层的方式，逐步填充矩阵的外圈，并不断收缩到内圈。

步骤：

1. 通过定义上下左右四个边界（即 startx、starty、offset），按顺时针方向依次填充每层的矩阵元素。
2. 每次循环都减少边界的范围，直到边界缩小到中心位置。
3. 如果矩阵的阶数 n 为奇数，最后剩下中心位置需要单独处理。

这是一种逐步推进的方式，按照顺时针方向填充矩阵，每次循环都会将一圈元素填满。

区间和问题

题目描述

给定一个长度为 n 的整数数组，要求计算多个区间的和。每次查询会给出两个整数 a 和 b，表示区间 [a, b]，程序需返回该区间内的元素之和。

解题思路

这个问题的核心在于如何高效计算多个区间的和。我们可以通过前缀和技巧来快速处理每次的查询。前缀和数组 p[i] 表示从数组的第一个元素到第 i 个元素的累加和。这样，对于任意区间 [a, b]，其区间和可以通过前缀和数组快速计算：

• 如果 a == 0，则区间和为 p[b]，即直接得到从第 0 到第 b 元素的累积和。
• 如果 a > 0，则区间和为 p[b] - p[a-1]，即减去 a 之前的累积和部分。

这种方法将每次查询的时间复杂度从 O(n) 降低到了 O(1)，大大提高了性能。

代码实现

import java.util.Scanner;

public class ArraySum {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();  // 读取数组长度
        int[] vec = new int[n];   // 原始数组
        int[] p = new int[n];     // 前缀和数组
        int presum = 0;           // 累积和变量

        // 构建前缀和数组
        for(int i = 0; i < n; i++) {
            vec[i] = input.nextInt();  // 读取数组元素
            presum += vec[i];
            p[i] = presum;
        }

        // 处理多次区间和查询
        while(input.hasNextInt()) {
            int a = input.nextInt();  // 起始位置
            int b = input.nextInt();  // 结束位置
            int sum = 0;

            // 通过前缀和计算区间和
            if (a == 0) {
                sum = p[b];
            } else {
                sum = p[b] - p[a - 1];
            }

            // 输出结果
            System.out.println(sum);
        }
        input.close();
    }
}

开发商购买土地问题

题目描述

开发商计划购买一块矩形土地，土地被分为 m * n 的格子，每个格子有一个整数表示该格子的价值。开发商希望找到一个方式将该土地划分为两部分，并使得这两部分的价值差最小。程序要求输出最小价值差。

解题思路

该问题可以通过逐步累积和的方式进行解决：

1. 首先，我们需要计算每行和每列的总价值，这样我们可以比较在每行或每列切分时的两部分价值差。
2. 对于每行累加求和 xp[i]，表示第 i 行的价值总和；对每列累加求和 yp[j]，表示第 j 列的价值总和。
3. 然后逐行和逐列累积行、列的总和，与整体价值总和的差值进行比较，得到最小的差值。

通过这种方法，我们可以通过不断尝试在不同位置切分土地，找到使得两部分价值差最小的位置。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();  // 行数
        int n = input.nextInt();  // 列数
        int[][] vec = new int[m][n];  // 土地价值矩阵
        int[] xp = new int[m];        // 每行累积价值
        int[] yp = new int[n];        // 每列累积价值

        int sum = 0;  // 总价值
        int presum = 0;

        // 计算每行的累积价值
        for(int i = 0; i < m; i++) {
            presum = 0;
            for (int j = 0; j < n; j++) {
                vec[i][j] = input.nextInt();
                sum += vec[i][j];     // 总价值
                presum += vec[i][j];  // 当前行累积价值
            }
            xp[i] = presum;  // 保存当前行的累积价值
        }

        // 计算每列的累积价值
        for (int j = 0; j < n; j++) {
            presum = 0;
            for (int i = 0; i < m; i++) {
                presum += vec[i][j];  // 当前列累积价值
            }
            yp[j] = presum;  // 保存当前列的累积价值
        }

        int xsum = 0;
        int result = Integer.MAX_VALUE;

        // 找出最小行切割差值
        for (int i = 0; i < m; i++) {
            xsum += xp[i];
            result = Math.min(result, Math.abs(sum - 2 * xsum));
        }

        int ysum = 0;

        // 找出最小列切割差值
        for (int j = 0; j < n; j++) {
            ysum += yp[j];
            result = Math.min(result, Math.abs(sum - 2 * ysum));
        }

        // 输出结果
        System.out.println(result);
        input.close();
    }
}