返回题库算法与数据结构刷题数组与哈希 · 第 3 / 3 篇

算法编程题：数组与哈希（10 题）

数组与哈希·10 道编程题#算法 #C##面试 #刷题 #编程题 #数组与哈希

007 判断整数数组是否包含重复值。

难度： 基础

方法签名： int[] numbers

输入约束： numbers 非 null

示例： [2, 1, 2] → true

目标复杂度： 平均时间 O(n)，额外空间 O(n)

查看参考答案

解题思路： 扫描时把值加入集合，Add 返回 false 时发现重复。

不变量： 集合包含当前位置之前出现过的所有不同值。

public static class AlgCode007Solution
{
    public static bool Solve(int[] numbers)
    {
        var seen = new HashSet<int>();
        foreach (int value in numbers)
        {
            if (!seen.Add(value)) return true;
        }
        return false;
    }
}

复杂度： 平均时间 O(n)，额外空间 O(n)。

边界用例： 空数组；单元素；负数；全部相同。

面试追问：

如果输入值域很小，能否用位图减少常数开销？

008 返回数组中和为目标值的两个元素索引。

难度： 进阶

方法签名： int[] numbers, int target

输入约束： numbers 非 null，恰好存在一组答案，同一元素不能使用两次

示例： [3, 8, 4], 12 → [1, 2]

目标复杂度： 平均时间 O(n)，额外空间 O(n)

查看参考答案

解题思路： 扫描时先查询互补值，再保存当前值的索引。

不变量： 字典只包含当前位置之前的元素。

public static class AlgCode008Solution
{
    public static int[] Solve(int[] numbers, int target)
    {
        var indexByValue = new Dictionary<int, int>();
        for (int index = 0; index < numbers.Length; index++)
        {
            long complement = (long)target - numbers[index];
            if (complement >= int.MinValue &&
                complement <= int.MaxValue &&
                indexByValue.TryGetValue((int)complement, out int other))
            {
                return [other, index];
            }
            indexByValue[numbers[index]] = index;
        }
        return [];
    }
}

复杂度： 平均时间 O(n)，额外空间 O(n)。

边界用例： 重复值；负数；互补值计算溢出。

面试追问：

如果数组已经有序，如何把额外空间降为 O(1)？

009 求两个数组的交集并保留重复次数。

难度： 进阶

方法签名： int[] first, int[] second

输入约束： 两个数组均非 null，结果顺序不作要求

示例： [1,2,2,3], [2,2,4] → [2,2]

目标复杂度： 平均时间 O(n+m)，额外空间 O(min(n,m))

查看参考答案

解题思路： 统计较短数组的频次，扫描另一个数组并消耗计数。

不变量： 字典中的计数表示尚未被结果使用的可匹配次数。

public static class AlgCode009Solution
{
    public static int[] Solve(int[] first, int[] second)
    {
        if (first.Length > second.Length) return Solve(second, first);
        var counts = new Dictionary<int, int>();
        foreach (int value in first)
            counts[value] = counts.GetValueOrDefault(value) + 1;
        var result = new List<int>();
        foreach (int value in second)
        {
            if (counts.GetValueOrDefault(value) == 0) continue;
            result.Add(value);
            counts[value]--;
        }
        return result.ToArray();
    }
}

复杂度： 平均时间 O(n+m)，额外空间 O(min(n,m))。

边界用例： 任一数组为空；全部重复；没有交集。

面试追问：

如果两个数组都已排序，如何改用双指针？

010 原地把数组中的零移动到末尾并保持非零元素顺序。

难度： 基础

方法签名： int[] numbers

输入约束： numbers 非 null，允许修改输入

示例： [0,1,0,3,12] → [1,3,12,0,0]

目标复杂度： 时间 O(n)，额外空间 O(1)

查看参考答案

解题思路： 写指针维护下一个非零位置，扫描后补零。

不变量： [0,write) 保存已扫描元素中的全部非零值且顺序不变。

public static class AlgCode010Solution
{
    public static void Solve(int[] numbers)
    {
        int write = 0;
        foreach (int value in numbers)
        {
            if (value != 0) numbers[write++] = value;
        }
        while (write < numbers.Length) numbers[write++] = 0;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 空数组；没有零；全部为零。

面试追问：

如何用交换减少对已经位于正确位置元素的写入？

011 把数组向右旋转 K 个位置。

难度： 进阶

方法签名： int[] numbers, int k

输入约束： numbers 非 null，k >= 0，允许修改输入

示例： [1,2,3,4,5], 2 → [4,5,1,2,3]

目标复杂度： 时间 O(n)，额外空间 O(1)

查看参考答案

解题思路： 先整体反转，再分别反转前 K 段和剩余段。

不变量： 三次反转后两段内部顺序恢复且段位置交换。

public static class AlgCode011Solution
{
    public static void Solve(int[] numbers, int k)
    {
        if (numbers.Length == 0) return;
        k %= numbers.Length;
        Reverse(numbers, 0, numbers.Length - 1);
        Reverse(numbers, 0, k - 1);
        Reverse(numbers, k, numbers.Length - 1);
    }
    
    private static void Reverse(int[] values, int left, int right)
    {
        while (left < right)
            (values[left++], values[right--]) = (values[right], values[left]);
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 空数组；k 为 0；k 大于数组长度。

面试追问：

如果输入是只读数组，最直接的 O(n) 空间方案是什么？

012 批量回答不可变数组的闭区间和查询。

难度： 进阶

方法签名： int[] numbers, int[][] queries

输入约束： 每个查询满足 0 <= left <= right < numbers.Length

示例： [2,4,1], [[0,1],[1,2]] → [6,5]

目标复杂度： 预处理 O(n)，每次查询 O(1)

查看参考答案

解题思路： 构造长度 n+1 的 long 前缀和，再计算端点差。

不变量： prefix[i] 等于前 i 个元素之和。

public static class AlgCode012Solution
{
    public static long[] Solve(int[] numbers, int[][] queries)
    {
        var prefix = new long[numbers.Length + 1];
        for (int index = 0; index < numbers.Length; index++)
            prefix[index + 1] = prefix[index] + numbers[index];
        var result = new long[queries.Length];
        for (int index = 0; index < queries.Length; index++)
        {
            int left = queries[index][0];
            int right = queries[index][1];
            result[index] = prefix[right + 1] - prefix[left];
        }
        return result;
    }
}

复杂度： 预处理 O(n)，查询总时间 O(q)，额外空间 O(n+q)。

边界用例： 单元素区间；覆盖整个数组；和超过 int。

面试追问：

如果数组会频繁更新，应改用什么数据结构？

013 统计和等于 K 的连续子数组数量。

难度： 进阶

方法签名： int[] numbers, int k

输入约束： numbers 非 null，元素可为负数

示例： [1,1,1], 2 → 2

目标复杂度： 平均时间 O(n)，额外空间 O(n)

查看参考答案

解题思路： 统计已见前缀和频次，当前前缀减 K 即为匹配起点。

不变量： 字典包含当前位置之前所有前缀和的出现次数。

public static class AlgCode013Solution
{
    public static long Solve(int[] numbers, int k)
    {
        var counts = new Dictionary<long, long> { [0] = 1 };
        long prefix = 0;
        long result = 0;
        foreach (int value in numbers)
        {
            prefix += value;
            result += counts.GetValueOrDefault(prefix - k);
            counts[prefix] = counts.GetValueOrDefault(prefix) + 1;
        }
        return result;
    }
}

复杂度： 平均时间 O(n)，额外空间 O(n)。

边界用例： 空数组；负数；零；结果超过 int。

面试追问：

为什么存在负数时不能直接使用可变滑动窗口？

014 求未排序数组中最长连续整数序列的长度。

难度： 综合

方法签名： int[] numbers

输入约束： numbers 非 null

示例： [100,4,200,1,3,2] → 4

目标复杂度： 平均时间 O(n)，额外空间 O(n)

查看参考答案

解题思路： 只从没有前驱值的元素开始向后扩展序列。

不变量： 每条连续序列只会从其最小值开始被完整扫描一次。

public static class AlgCode014Solution
{
    public static int Solve(int[] numbers)
    {
        var values = new HashSet<int>(numbers);
        int best = 0;
        foreach (int value in values)
        {
            if (value != int.MinValue && values.Contains(value - 1)) continue;
            int length = 1;
            int current = value;
            while (current != int.MaxValue && values.Contains(current + 1))
            {
                current++;
                length++;
            }
            best = Math.Max(best, length);
        }
        return best;
    }
}

复杂度： 平均时间 O(n)，额外空间 O(n)。

边界用例： 空数组；重复值；int.MinValue 与 int.MaxValue。

面试追问：

排序后扫描的复杂度和空间取舍是什么？

015 返回保证存在的多数元素。

难度： 进阶

方法签名： int[] numbers

输入约束： numbers 非空，某个值出现次数严格大于 n/2

示例： [2,2,1,2] → 2

目标复杂度： 时间 O(n)，额外空间 O(1)

查看参考答案

解题思路： 使用 Boyer-Moore 抵消不同元素，剩余候选即多数元素。

不变量： count 表示当前前缀抵消后候选的净票数。

public static class AlgCode015Solution
{
    public static int Solve(int[] numbers)
    {
        int candidate = 0;
        int count = 0;
        foreach (int value in numbers)
        {
            if (count == 0) candidate = value;
            count += value == candidate ? 1 : -1;
        }
        return candidate;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 单元素；多数元素分散；契约不保证存在时需二次验证。

面试追问：

如果题目不保证多数元素存在，如何验证候选？

016 在线性时间内找到缺失的第一个正整数。

难度： 综合

方法签名： int[] numbers

输入约束： numbers 非 null，允许修改输入

示例： [3,4,-1,1] → 2

目标复杂度： 时间 O(n)，额外空间 O(1)

查看参考答案

解题思路： 把范围 [1,n] 的值交换到下标 value-1，随后找首个错位。

不变量： 每次交换至少把一个合法值放到目标位置，重复值不会无限交换。

public static class AlgCode016Solution
{
    public static int Solve(int[] numbers)
    {
        int index = 0;
        while (index < numbers.Length)
        {
            int value = numbers[index];
            int target = value - 1;
            if (value > 0 &&
                value <= numbers.Length &&
                numbers[target] != value)
            {
                (numbers[index], numbers[target]) =
                    (numbers[target], numbers[index]);
            }
            else
            {
                index++;
            }
        }
        for (index = 0; index < numbers.Length; index++)
            if (numbers[index] != index + 1) return index + 1;
        return numbers.Length + 1;
    }
}

复杂度： 时间 O(n)，额外空间 O(1)。

边界用例： 空数组；重复值；全部为负；已经包含 1 到 n。

面试追问：

为什么每个元素参与的交换次数总体仍是 O(n)？