Google 面试经验分享：连续子数组判断算法题 - Oavoservice

🎤 Google 0520 面经

👩‍💻 Candidate 在 Google 面试中遇到了一个经典的连续子数组判断算法题。

📋 题目要求

给定一个不可变数据类型 Item 和两个 Item 数组 array 与 possibleSubArray，判断possibleSubArray 是否作为连续子数组完整地出现在 array 中。

📝 具体说明

• 需要判断 possibleSubArray 是否是 array 的连续子数组
• 子数组必须是连续的，不能跳跃
• 元素顺序必须完全一致
• Item 是不可变数据类型，需要重写 equals 方法

❓ 问题分析

这是一个典型的字符串匹配问题的变种：

• 核心思想：在数组中寻找连续的子序列
• 关键点：需要逐个比较元素
• 优化：可以使用KMP算法优化时间复杂度

💡 思路设计

使用滑动窗口方法：

1. 遍历主数组 array
2. 对于每个位置，检查是否匹配子数组的第一个元素
3. 如果匹配，继续检查后续元素
4. 如果完全匹配，返回 true

💻 代码实现

// 不可变数据类型 Item
class Item {
    private final int value;
    
    public Item(int value) {
        this.value = value;
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Item item = (Item) obj;
        return value == item.value;
    }
    
    @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }
    
    @Override
    public String toString() {
        return String.valueOf(value);
    }
}

public class ContinuousSubarrayChecker {
    
    // 方法1：暴力解法 O(n*m)
    public boolean isContinuousSubarray(Item[] array, Item[] possibleSubArray) {
        if (possibleSubArray == null || possibleSubArray.length == 0) {
            return true; // 空数组是任何数组的子数组
        }
        
        if (array == null || array.length < possibleSubArray.length) {
            return false;
        }
        
        int n = array.length;
        int m = possibleSubArray.length;
        
        // 遍历主数组的每个可能起始位置
        for (int i = 0; i <= n - m; i++) {
            boolean found = true;
            
            // 检查从位置i开始的连续m个元素
            for (int j = 0; j < m; j++) {
                if (!array[i + j].equals(possibleSubArray[j])) {
                    found = false;
                    break;
                }
            }
            
            if (found) {
                return true;
            }
        }
        
        return false;
    }
    
    // 方法2：KMP算法优化 O(n+m)
    public boolean isContinuousSubarrayKMP(Item[] array, Item[] possibleSubArray) {
        if (possibleSubArray == null || possibleSubArray.length == 0) {
            return true;
        }
        
        if (array == null || array.length < possibleSubArray.length) {
            return false;
        }
        
        // 构建next数组
        int[] next = buildNextArray(possibleSubArray);
        
        int i = 0; // 主数组指针
        int j = 0; // 子数组指针
        
        while (i < array.length && j < possibleSubArray.length) {
            if (array[i].equals(possibleSubArray[j])) {
                i++;
                j++;
            } else if (j > 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }
        
        return j == possibleSubArray.length;
    }
    
    // 构建KMP算法的next数组
    private int[] buildNextArray(Item[] pattern) {
        int[] next = new int[pattern.length];
        int j = 0;
        
        for (int i = 1; i < pattern.length; i++) {
            while (j > 0 && !pattern[i].equals(pattern[j])) {
                j = next[j - 1];
            }
            
            if (pattern[i].equals(pattern[j])) {
                j++;
            }
            
            next[i] = j;
        }
        
        return next;
    }
    
    // 测试方法
    public static void main(String[] args) {
        ContinuousSubarrayChecker checker = new ContinuousSubarrayChecker();
        
        // 测试用例1：正常情况
        Item[] array1 = {
            new Item(1), new Item(2), new Item(3), new Item(4), new Item(5)
        };
        Item[] subArray1 = {
            new Item(2), new Item(3), new Item(4)
        };
        System.out.println("测试1: " + checker.isContinuousSubarray(array1, subArray1)); // true
        
        // 测试用例2：不连续的情况
        Item[] array2 = {
            new Item(1), new Item(2), new Item(4), new Item(3), new Item(5)
        };
        Item[] subArray2 = {
            new Item(2), new Item(3), new Item(4)
        };
        System.out.println("测试2: " + checker.isContinuousSubarray(array2, subArray2)); // false
        
        // 测试用例3：空子数组
        Item[] subArray3 = {};
        System.out.println("测试3: " + checker.isContinuousSubarray(array1, subArray3)); // true
        
        // 测试用例4：单个元素
        Item[] subArray4 = {new Item(3)};
        System.out.println("测试4: " + checker.isContinuousSubarray(array1, subArray4)); // true
        
        // 测试KMP算法
        System.out.println("KMP测试1: " + checker.isContinuousSubarrayKMP(array1, subArray1)); // true
        System.out.println("KMP测试2: " + checker.isContinuousSubarrayKMP(array2, subArray2)); // false
    }
}

🔍 算法分析

• 暴力解法时间复杂度：O(n*m)，其中n是主数组长度，m是子数组长度
• KMP算法时间复杂度：O(n+m)
• 空间复杂度：O(m)（KMP算法的next数组）
• 核心思想：滑动窗口 + 字符串匹配算法

📊 测试用例

// 测试用例1：正常匹配
array = [1, 2, 3, 4, 5]
possibleSubArray = [2, 3, 4]
期望输出：true

// 测试用例2：不匹配
array = [1, 2, 4, 3, 5]
possibleSubArray = [2, 3, 4]
期望输出：false

// 测试用例3：空子数组
array = [1, 2, 3, 4, 5]
possibleSubArray = []
期望输出：true

// 测试用例4：单个元素
array = [1, 2, 3, 4, 5]
possibleSubArray = [3]
期望输出：true

// 测试用例5：子数组长度大于主数组
array = [1, 2]
possibleSubArray = [1, 2, 3]
期望输出：false

🚀 优化思路

面试官可能会问如何优化：

• KMP算法：避免重复比较，时间复杂度从O(n*m)降到O(n+m)
• 哈希优化：如果Item类型支持，可以使用哈希值快速比较
• 并行处理：对于大数据集，可以考虑并行搜索

✨ 面试官反馈

面试官对解决方案很满意："Great solution! You've provided both the straightforward approach and the optimized KMP algorithm. The code is clean and handles edge cases well."

面试技巧分享

在 Google 面试中，除了算法实现，面试官还会关注：

1. 问题理解能力

能够准确理解题目要求，特别是"连续子数组"的概念。

2. 边界条件处理

考虑空数组、单个元素、长度不匹配等特殊情况。

3. 算法优化思维

主动提出KMP算法等优化方案，展现算法知识深度。

4. 代码质量

写出清晰、可读的代码，包含适当的注释和测试用例。

Oavoservice 实时辅助服务

在这次 Google 面试中，我们的实时辅助系统发挥了关键作用：

• 问题分析：帮助候选人快速理解连续子数组的概念
• 算法指导：提供暴力解法和KMP优化方案
• 代码实现：协助完成完整的代码实现
• 测试验证：确保所有测试用例都能正确通过

结语

连续子数组判断虽然是一道基础算法题，但考察了候选人对数组操作、字符串匹配算法的理解。在面试中，能够提供多种解法并分析其优缺点，展现了候选人的技术深度和优化思维。

如果你正在准备 Google 或其他公司的技术面试，欢迎联系 Oavoservice。我们拥有丰富的面试经验和专业的辅助团队，能够在你最需要的时候提供及时有效的帮助。

Oavoservice - 让每一次面试都成为成功的机会！

需要辅助的同学随时dd哦，vo开始前支持mock！