Java滑动窗口实现从nums中选出不相交子数组匹配groups

给你一个长度为 n 的二维整数数组 groups ，同时给你一个整数数组 nums 。

你是否可以从 nums 中选出 n 个 不相交 的子数组，使得第 i 个子数组与 groups[i] （下标从 0 开始）完全相同，且如果 i > 0 ，那么第 (i-1) 个子数组在 nums 中出现的位置在第 i 个子数组前面。（也就是说，这些子数组在 nums 中出现的顺序需要与 groups 顺序相同）

如果你可以找出这样的 n 个子数组，请你返回 true ，否则返回 false 。

如果不存在下标为 k 的元素 nums[k] 属于不止一个子数组，就称这些子数组是 不相交 的。子数组指的是原数组中连续元素组成的一个序列。java滑动窗口实现

要解决这个问题，我们可以使用滑动窗口技术来检查 nums 中是否存在与 groups 中每个子数组匹配的子数组，并且这些子数组是按顺序出现且不相交的。以下是一个 Java 实现：

public class Solution {
    public boolean canChoose(int[][] groups, int[] nums) {
        int n = nums.length;
        int start = 0; // 记录当前在 nums 中的起始位置

        for (int[] group : groups) {
            boolean found = false;
            // 在 nums 中找到一个与当前 group 匹配的子数组
            for (int i = start; i <= n - group.length; i++) {
                if (matches(nums, i, group)) {
                    found = true;
                    start = i + group.length; // 更新起始位置，确保子数组不相交
                    break;
                }
            }
            if (!found) {
                return false; // 如果找不到匹配的子数组，返回 false
            }
        }
        return true; // 所有子数组都找到匹配，返回 true
    }

    // 检查 nums 从 start 开始的子数组是否与 group 匹配
    private boolean matches(int[] nums, int start, int[] group) {
        for (int i = 0; i < group.length; i++) {
            if (nums[start + i] != group[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] groups = {{1, 2, 3}, {3, 4}};
        int[] nums = {7, 1, 2, 3, 4, 3, 4};
        System.out.println(solution.canChoose(groups, nums)); // 输出 true

        int[][] groups2 = {{1, 2, 3}, {3, 4}};
        int[] nums2 = {7, 1, 2, 3, 4, 3, 5};
        System.out.println(solution.canChoose(groups2, nums2)); // 输出 false
    }
}

解释

1. 主方法 canChoose:

   • start 变量用于记录当前在 nums 中的起始位置。
   • 对于每个 group，我们在 nums 中从 start 开始查找一个匹配的子数组。
   • 如果找到匹配的子数组，更新 start 以确保子数组不相交。
   • 如果找不到匹配的子数组，返回 false。
   • 如果所有 group 都找到匹配的子数组，返回 true。

2. 辅助方法 matches:

   • 检查 nums 从 start 开始的子数组是否与 group 匹配。
   • 如果所有元素都匹配，返回 true，否则返回 false。

测试

• 在 main 方法中，我们测试了两个例子：
  • 第一个例子中，groups 中的子数组可以在 nums 中找到且不相交，返回 true。
  • 第二个例子中，groups 中的子数组不能在 nums 中找到，返回 false。