暴力枚举算法：核心思想与经典例题实战

案例二：盛最多水的容器

这道题在力扣上非常经典，展示了暴力解法与双指针优化的对比。

暴力枚举解法 使用双重循环遍历所有左右边界组合，计算面积并取最大值。时间复杂度 O(n²)，在数据量大时容易超时。

// 辅助函数：求两个数的较小值
int min(int a, int b) {
    return a < b ? a : b;
}

int maxArea(int* height, int heightSize) {
    int max_water = 0;
    // 外层循环：确定左边界 i
    for (int i = 0; i < heightSize - 1; i++) {
        // 内层循环：确定右边界 j
        for (int j = i + 1; j < heightSize; j++) {
            // 1. 计算当前容器的高度（受限于较短的一边）
            int current_height = min(height[i], height[j]);
            // 2. 计算当前容器的宽度
            int current_width = j - i;
            // 3. 计算当前面积
            int current_area = current_height * current_width;
            // 4. 如果当前面积比历史最大值大，则更新
            if (current_area > max_water) {
                max_water = current_area;
            }
        }
    }
    return max_water;
}

最优解：双指针 通过从两端向中间收缩，可以在 O(n) 时间内解决问题。这里为了演示宏定义的使用，使用了预处理器宏。

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

int maxArea(int* height, int heightSize) {
    int ret = 0;
    int l = 0;
    int r = heightSize - 1;
    while (l < r) {
        int current_height = MIN(height[l], height[r]);
        int current_Water = current_height * (r - l);
        ret = MAX(ret, current_Water);
        
        // 移动较短的一边，试图寻找更高的边界
        if (height[l] < height[r]) {
            ++l;
        } else {
            --r;
        }
    }
    return ret;
}

案例三：两数之和

给定一个整数数组和一个目标值，找出和为目标值的两个数的下标。

解题思路 暴力枚举的核心是检查数组中每一个可能的数对组合。外层循环固定第一个数，内层循环寻找第二个数。

#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    // 外层循环：遍历第一个数
    for (int i = 0; i < numsSize; i++) {
        // 内层循环：遍历第二个数，从 i+1 开始避免重复
        for (int j = i + 1; j < numsSize; j++) {
            // 判断两数之和是否等于目标值
            if (nums[i] + nums[j] == target) {
                // 分配内存用于存储结果（需要存放 2 个 int）
                int* result = (int*)malloc(2 * sizeof(int));
                if (result == NULL) {
                    *returnSize = 0;
                    return NULL;
                }
                // 存入下标
                result[0] = i;
                result[1] = j;
                // 设置返回数组的大小为 2
                *returnSize = 2;
                // 返回结果指针
                return result;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

注意

• malloc 分配的内存需要在调用方释放，避免内存泄漏。
• 指针访问方式 result[0] 等价于 *(result + 0)，理解这一点有助于处理动态数组。

案例四：数字特征统计

统计 0 到 20250412 之间，包含至少 1 个 0、2 个 2、1 个 5 的数字个数。

#include <iostream>
using namespace std;

bool check(int num) {
    int c0 = 0, c2 = 0, c5 = 0;
    // 逐步取出最后一个数字
    while (num > 0) {
        int digit = num % 10;
        if (digit == 0) c0++;
        else if (digit == 2) c2++;
        else if (digit == 5) c5++;
        num /= 10;
    }
    // 条件：至少 1 个 0，2 个 2，1 个 5
    return (c2 >= 2) && (c0 >= 1) && (c5 >= 1);
}

int main() {
    int count = 0;
    // 遍历检查范围内的每个数
    for (int i = 0; i <= 20250412; i++) {
        if (check(i)) {
            count++;
        }
    }
    cout << "满足条件的数的数量为：" << count << endl;
    return 0;
}

总结

暴力枚举虽然简单，但它是理解算法复杂度的基石。在实际开发中，我们首先要考虑的是数据规模：如果 N 很小，暴力法完全可行；如果 N 很大，就需要思考是否有贪心、动态规划或双指针等优化空间。掌握这些基础案例，能为后续学习更复杂的算法打下坚实基础。