力扣hot100刷题——0~10

news/2025/2/23 11:14:16

文章目录

  • 1.两数之和
    • 题目描述
    • 思路一：哈希
    • 代码
    • 思路二：暴力
    • 代码
  • 2.字母异位词分组
    • 题目描述
    • 思路：哈希(待改进)
    • 代码
  • 3.最长连续序列
    • 题目描述
    • 思路：排序
    • code
  • 4.移动零
    • 题目描述
    • 思路：双指针
    • code
  • 5.盛最多水的容器
    • 题目描述
    • 思路：双指针
    • code
    • code(优化)
  • 6.三数之和
    • 题目描述
    • 思路：排序+双指针
    • code
  • 7.接雨水
    • 题目描述
    • 思路一：dp
    • code
    • 思路二：双指针
    • code
  • 8.无重复的字符的最长子串
    • 题目描述
    • 思路：滑动窗口
    • code
  • 9.找到字符串中所有字母异位词
    • 题目描述
    • 思路：滑动窗口+字符频率统计
    • code
  • 10.和为K的子数组
    • 题目描述
    • 思路：哈希表+前缀和
    • code Ⅰ(数组模拟哈希)
    • code Ⅱ

1.两数之和

题目描述

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

思路一：哈希

1.创建哈希表：

  • 使用一个

    哈希表（键值对存储）

    来存放遍历过的数组元素：

    • 键（Key）：数组元素的值 nums[i]
    • 值（Value）：该元素的索引 i

2.遍历数组：

  • 对于当前元素 nums[i]，计算 需要的补数： num=target−nums[i]\text{num} = \text{target} - \text{nums}[i]num=target−nums[i]
  • 检查哈希表：
    • 如果 num 已经在哈希表中：
      • 说明 nums[i] + num == target，即找到了答案。
      • 返回当前索引 i 和补数 num 的索引（哈希表中存储的索引）。
    • 否则，将当前 nums[i] 存入哈希表：
      • 记录 nums[i] 及其索引 i，以便后续查找。

3.返回答案：

  • 由于题目保证有解，不需要额外处理无解情况。

代码

#include <stdio.h>
#include <stdlib.h>


// 定义哈希表节点
typedef struct {
    int val;        // 存储值（作为哈希键）
    int key;        // 存储索引
    UT_hash_handle hh; // uthash 句柄，用于哈希表管理
} HashNode;

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;  // 题目要求返回两个索引
    int* ans = (int*)malloc(sizeof(int) * 2);  // 申请数组存储索引结果
    if (!ans) return NULL;  // 检查 malloc 是否成功，避免内存分配失败

    HashNode* h = NULL;  // 定义哈希表指针，初始为空

    // 遍历 nums 数组
    for (int i = 0; i < numsSize; i++) {
        HashNode *t;
        int num = target - nums[i];  // 计算需要查找的补数

        // 在哈希表中查找 `num` 是否已经存在
        HASH_FIND_INT(h, &num, t);
        if (t != NULL) {  // 找到匹配项
            ans[0] = i;       // 当前索引
            ans[1] = t->key;  // 之前存入哈希表的索引

            // 释放哈希表内存，防止内存泄漏
            HashNode *current, *tmp;
            HASH_ITER(hh, h, current, tmp) {
                HASH_DEL(h, current);  // 从哈希表删除节点
                free(current);         // 释放内存
            }

            return ans;  // 返回索引数组
        }

        // 如果未找到，则将当前值及其索引存入哈希表
        HashNode* p = (HashNode*)malloc(sizeof(HashNode));
        if (!p) {  // 检查 malloc 是否成功
            free(ans); // 释放已分配的数组，避免内存泄漏
            return NULL;
        }
        p->key = i;      // 存储当前索引
        p->val = nums[i]; // 存储当前值
        HASH_ADD_INT(h, val, p); // 插入到哈希表
    }

    // 释放哈希表内存（理论上不会执行到这里，因为题目保证有解）
    HashNode *current, *tmp;
    HASH_ITER(hh, h, current, tmp) {
        HASH_DEL(h, current);
        free(current);
    }

    return ans;  // 返回最终结果（理论上不会执行到这里）
}

思路二：暴力

两层for循环遍历寻找答案，本题可以AC

代码

#include <stdio.h>
#include <stdlib.h>

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;  // 默认返回 2 个索引
    int *ans = (int*)malloc(sizeof(int) * 2);  // 申请内存
    if (!ans) return NULL;  // 确保 malloc 成功
    
    // 暴力枚举所有可能的两个数对
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {  // 发现符合条件的两个数
                ans[0] = i;
                ans[1] = j;
                return ans;  // 直接返回
            }
        }
    }

    // 如果没有找到答案，释放内存并返回 NULL
    free(ans);
    *returnSize = 0;  // 设置 returnSize 为 0，表示无解
    return NULL;
}

2.字母异位词分组

题目描述

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

思路：哈希(待改进)

  • 使用哈希表（hash 数组）记录每个字符串的字符频率统计。
  • 遍历字符串数组，对每个字符串计算其字符频率统计。
  • 检查当前字符频率统计是否已存在于哈希表中：
    • 如果存在，则将当前字符串加入对应的分组。
    • 如果不存在，则创建新的分组，并将当前字符串作为该组的第一个元素。
  • 最终返回分组结果。

代码

/**
 * 返回一个大小为 *returnSize 的数组，数组中的每个元素是一个字符串数组。
 * 每个字符串数组的大小通过 *returnColumnSizes 数组返回。
 * 注意：返回的数组和 *returnColumnSizes 数组必须动态分配内存，调用者负责释放。
 */
char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) {
    // 分配结果数组的内存，最多有 strsSize 个分组
    char ***ans = malloc(sizeof(char**) * strsSize);
    // 分配哈希表的内存，用于存储每个分组的字符频率统计
    int **hash = malloc(sizeof(int*) * strsSize);
    // 初始化返回的分组数量为 0
    *returnSize = 0;
    // 分配 returnColumnSizes 的内存，用于存储每个分组的大小
    *returnColumnSizes = malloc(sizeof(int) * strsSize);

    // 遍历每个字符串
    for (int i = 0; i < strsSize; i++) {
        // 分配内存并初始化字符频率统计数组 t
        int *t = malloc(sizeof(int) * 26);
        for (int j = 0; j < 26; j++) t[j] = 0; // 初始化为 0

        // 计算当前字符串的字符频率统计
        for (int j = 0; strs[i][j] != '\0'; j++) {
            t[strs[i][j] - 'a']++; // 统计每个字符的出现次数
        }

        // 检查当前字符频率统计是否已存在于哈希表中
        bool find = false;
        for (int k = 0; k < *returnSize; k++) {
            bool flag = true;
            // 比较当前字符频率统计 t 和哈希表中的统计 hash[k]
            for (int j = 0; j < 26; j++) {
                if (t[j] != hash[k][j]) {
                    flag = false; // 如果不匹配，标记为 false
                    break;
                }
            }
            // 如果找到匹配的分组
            if (flag) {
                find = true;
                // 将当前字符串加入分组 ans[k]
                ans[k][(*returnColumnSizes)[k]] = strs[i];
                (*returnColumnSizes)[k]++; // 更新分组大小
                break;
            }
        }

        // 如果未找到匹配的分组
        if (!find) {
            // 将当前字符频率统计加入哈希表
            hash[(*returnSize)] = t;
            // 分配内存并初始化新的分组
            ans[(*returnSize)] = malloc(sizeof(char*) * strsSize);
            ans[(*returnSize)][0] = strs[i]; // 将当前字符串作为分组的第一个元素
            (*returnColumnSizes)[*returnSize] = 1; // 初始化分组大小为 1
            (*returnSize)++; // 增加分组数量
        }
    }

    // 返回分组结果
    return ans;
}

3.最长连续序列

题目描述

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：

输入：nums = [1,0,1,2]
输出：3

思路：排序

步骤：

  1. 排序：
    • 使用 qsort 对数组进行排序，时间复杂度为 O ( n l o g ⁡ n ) O(nlog⁡n) O(nlog⁡n)。
  2. 查找最长连续序列：
    • 遍历排序后的数组，统计连续序列的长度。
    • 如果当前元素与下一个元素差为 1，则增加计数。
    • 如果当前元素与下一个元素相等，则跳过重复元素。

code

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于 qsort
int cmp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

// 查找最长连续序列的长度
int longestConsecutive(int* nums, int numsSize) {
    // 如果数组为空，直接返回 0
    if (numsSize == 0) return 0;

    // 对数组进行排序
    qsort(nums, numsSize, sizeof(int), cmp);

    int ans = 0; // 最终结果
    int i = 0;   // 遍历指针

    while (i < numsSize) {
        int j = i; // 当前连续序列的起始位置
        int cnt = 1; // 当前连续序列的长度

        // 检查下一个元素是否构成连续序列
        while (j < numsSize - 1 && (nums[j + 1] == nums[j] + 1 || nums[j + 1] == nums[j])) {
            if (nums[j + 1] == nums[j] + 1) {
                cnt++; // 如果差为 1，增加计数
            }
            j++; // 移动指针
        }

        // 更新最长连续序列的长度
        ans = fmax(ans, cnt);
        i = j + 1; // 跳过已处理的连续序列
    }

    return ans;
}

4.移动零

题目描述

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

思路：双指针

双指针：

  • 使用指针 j 来记录非零元素的位置。
  • 遍历数组，当遇到非零元素时，将其移动到 nums[j]，然后递增 j。
  • 最后将剩余的位置填充为 0。

code

void moveZeroes(int* nums, int numsSize) {
    int j = 0; // 指向下一个非零元素应该放置的位置

    // 将非零元素移动到数组前面
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] != 0) {
            nums[j++] = nums[i];
        }
    }

    // 将剩余的位置填充为 0
    while (j < numsSize) {
        nums[j++] = 0;
    }
}

5.盛最多水的容器

题目描述

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

img

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

思路：双指针

  1. 双指针：
    • 使用两个指针 l 和 r，分别指向数组的开头和结尾。
    • 计算当前容器的面积：(r - l) * min(height[l], height[r])。
    • 移动高度较小的指针，因为容器的面积受限于较短的一边。
  2. 优化移动指针：
    • 在移动指针时，跳过所有比当前高度更小的柱子，因为这些柱子不可能形成更大的面积。

code

#include <stdio.h>
#include <stdlib.h>
// 盛最多水的容器
int maxArea(int* height, int heightSize) {
    // 初始化结果，计算最左边和最右边柱子的面积
    int ans = (heightSize - 1) * fmin(height[0], height[heightSize - 1]);
    int l = 0, r = heightSize - 1; // 双指针

    while (l < r) {
        if (height[l] < height[r]) {
            // 如果左边柱子较矮，移动左指针
            int i = l + 1;
            // 跳过所有比当前柱子更矮的柱子
            while (i < r && height[i] <= height[l]) i++;
            if (i == r) break; // 如果已经到达右边界，退出循环
            l = i; // 更新左指针
        } else {
            // 如果右边柱子较矮，移动右指针
            int i = r - 1;
            // 跳过所有比当前柱子更矮的柱子
            while (i > l && height[i] <= height[r]) i--;
            if (i == l) break; // 如果已经到达左边界，退出循环
            r = i; // 更新右指针
        }
        // 计算当前面积并更新结果
        ans = fmax(ans, (r - l) * fmin(height[l], height[r]));
    }

    return ans;
}

code(优化)

#include <stdio.h>
#include <stdlib.h>


// 盛最多水的容器
int maxArea(int* height, int heightSize) {
    int ans = 0; // 初始化结果
    int l = 0, r = heightSize - 1; // 双指针

    while (l < r) {
        // 计算当前面积并更新结果
        ans = fmax(ans, (r - l) * fmin(height[l], height[r]));

        // 移动较矮的指针
        if (height[l] < height[r]) {
            l++; // 移动左指针
        } else {
            r--; // 移动右指针
        }
    }

    return ans;
}

6.三数之和

题目描述

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

思路：排序+双指针

  1. 排序：
    • 首先对数组进行升序排序，方便后续使用双指针法。
  2. 固定一个数，转化为两数之和问题：
    • 遍历数组，固定一个数 nums[i]，将问题转化为在剩余数组中寻找两个数 nums[l] 和 nums[r]，使得 nums[l] + nums[r] = -nums[i]。
  3. 双指针法：
    • 使用双指针 l 和 r，分别指向剩余数组的起始和末尾。
    • 根据当前和 nums[l] + nums[r] 与目标值 -nums[i] 的关系，移动指针：
      • 如果和小于目标值，左指针 l 右移。
      • 如果和大于目标值，右指针 r 左移。
      • 如果和等于目标值，记录该三元组。
  4. 去重：
    • 在遍历过程中，跳过重复的 nums[i]，避免重复的三元组。
    • 在找到满足条件的三元组后，跳过重复的 nums[l] 和 nums[r]。
  5. 返回结果：
    • 将所有满足条件的三元组存储到结果数组中，并返回。

code

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

// 升序排列的比较函数
int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    // 首先对数组进行排序
    qsort(nums, numsSize, sizeof(int), cmp);

    // 初始化返回的数组大小和列大小数组
    *returnSize = 0;
    *returnColumnSizes = malloc(sizeof(int) * numsSize * numsSize); // 分配足够大的空间
    int **ans = malloc(sizeof(int*) * numsSize * numsSize); // 分配足够大的空间

    // 遍历数组，寻找三数之和为0的组合
    for (int i = 0; i < numsSize - 2; i++) { // 注意边界条件，i < numsSize - 2
        if (nums[i] > 0) break; // 如果当前数大于0，后面的数都大于0，不可能有三数之和为0

        // 跳过重复的元素
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int target = -nums[i]; // 目标值为当前数的相反数
        int l = i + 1, r = numsSize - 1; // 双指针初始化

        while (l < r) {
            int sum = nums[l] + nums[r];

            if (sum < target) {
                l++; // 如果和小于目标值，左指针右移
            } else if (sum > target) {
                r--; // 如果和大于目标值，右指针左移
            } else {
                // 找到满足条件的三元组
                ans[*returnSize] = malloc(sizeof(int) * 3);
                ans[*returnSize][0] = nums[i];
                ans[*returnSize][1] = nums[l];
                ans[*returnSize][2] = nums[r];
                (*returnColumnSizes)[*returnSize] = 3;
                (*returnSize)++;

                // 跳过重复的元素
                while (l < r && nums[l] == nums[l + 1]) l++;
                while (l < r && nums[r] == nums[r - 1]) r--;

                // 移动指针
                l++;
                r--;
            }
        }
    }

    return ans;
}

7.接雨水

题目描述

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

img

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

思路一：dp

  1. 预处理：
    • 从左到右遍历数组，记录每个位置左侧的最大高度 dp[i][0]。
    • 从右到左遍历数组，记录每个位置右侧的最大高度 dp[i][1]。
  2. 计算雨水量：
    • 对于每个位置 i，雨水量为 min(dp[i][0], dp[i][1]) - height[i]。
    • 将所有位置的雨水量累加。

code

int trap(int* height, int heightSize) {
    // 动态规划数组：dp[i][0] 表示位置 i 左侧的最大高度，dp[i][1] 表示位置 i 右侧的最大高度
    int dp[heightSize][2];
    memset(dp, 0, sizeof(dp)); // 初始化 dp 数组为 0

    // 计算每个位置左侧的最大高度
    int Max = 0; // 用于记录当前左侧的最大高度
    for (int i = 0; i < heightSize; i++) {
        dp[i][0] = fmax(height[i], Max); // 更新 dp[i][0] 为当前高度和左侧最大高度的较大值
        Max = fmax(Max, height[i]); // 更新左侧最大高度
    }

    // 计算每个位置右侧的最大高度
    Max = 0; // 重置 Max，用于记录当前右侧的最大高度
    for (int i = heightSize - 1; i >= 0; i--) {
        dp[i][1] = fmax(height[i], Max); // 更新 dp[i][1] 为当前高度和右侧最大高度的较大值
        Max = fmax(Max, height[i]); // 更新右侧最大高度
    }

    // 计算雨水量
    int ans = 0; // 用于记录总雨水量
    for (int i = 0; i < heightSize; i++) {
        // 每个位置的雨水量为左侧最大高度和右侧最大高度的较小值减去当前高度
        ans += (fmin(dp[i][0], dp[i][1]) - height[i]);
    }

    return ans; // 返回总雨水量
}

思路二：双指针

1.初始化：

  • 使用两个指针 left 和 right，分别指向数组的起始和末尾。
  • 使用两个变量 left_max 和 right_max，分别记录从左到右和从右到左的最大高度。

2.遍历数组：

  • 比较 height[left] 和 height[right]：
    • 如果 height[left] < height[right]：
      • 更新 left_max 为 max(left_max, height[left])。
      • 计算当前位置能接的雨水量：left_max - height[left]，并累加到结果中。
      • 左指针右移：left++。
    • 否则：
      • 更新 right_max 为 max(right_max, height[right])。
      • 计算当前位置能接的雨水量：right_max - height[right]，并累加到结果中。
      • 右指针左移：right--。

3.返回结果：

  • 最终累加的雨水量即为结果。

code

#include <stdio.h>
#include <stdlib.h>

// 返回接雨水的总量
int trap(int* height, int heightSize) {
    if (heightSize == 0) {
        return 0;
    }

    int left = 0, right = heightSize - 1; // 双指针
    int left_max = height[left], right_max = height[right]; // 左右最大高度
    int result = 0; // 接雨水的总量

    while (left < right) {
        // 如果左边高度小于右边高度
        if (height[left] < height[right]) {
            left++; // 左指针右移
            left_max = (left_max > height[left]) ? left_max : height[left]; // 更新左边最大高度
            result += left_max - height[left]; // 计算当前列的雨水量
        }
        // 如果右边高度小于等于左边高度
        else {
            right--; // 右指针左移
            right_max = (right_max > height[right]) ? right_max : height[right]; // 更新右边最大高度
            result += right_max - height[right]; // 计算当前列的雨水量
        }
    }

    return result;
}

8.无重复的字符的最长子串

题目描述

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路：滑动窗口

  1. 滑动窗口：
    • 使用两个指针 left 和 right 表示滑动窗口的左右边界。
    • right 指针用于扩展窗口，left 指针用于收缩窗口。
  2. 哈希表：
    • 使用一个哈希表记录当前窗口中的字符。
    • 当 right 指针指向的字符未出现在集合中时，将其加入集合，并扩展窗口。
    • 当 right 指针指向的字符已出现在集合中时，移动 left 指针，直到移除重复字符。
  3. 更新结果：
    • 在每次扩展窗口后，更新最长子串的长度。

code

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

int lengthOfLongestSubstring(char* s) {
    int ans = 0; // 记录最长子串的长度
    int n = strlen(s); // 字符串长度
    if (n <= 1) return n; // 如果字符串长度为 0 或 1，直接返回

    // 使用一个哈希集合（数组）来记录字符是否出现过
    // ASCII 字符共有 128 个，因此数组大小为 128
    bool flag[128];
    memset(flag, false, sizeof(flag)); // 初始化哈希集合

    int l = 0, r = 0; // 滑动窗口的左右指针
    while (r < n) {
        // 如果当前字符 s[r] 未出现过
        if (!flag[s[r]]) {
            flag[s[r]] = true; // 标记为已出现
            r++; // 右指针右移
        }
        // 如果当前字符 s[r] 已经出现过
        else {
            ans = fmax(ans, r - l); // 更新最长子串的长度
            // 移动左指针，直到移除重复字符
            while (s[l] != s[r]) {
                flag[s[l]] = false; // 移除左指针指向的字符
                l++; // 左指针右移
            }
            l++; // 左指针移动到重复字符的下一个位置
            r++; // 右指针右移
        }
    }
    ans = fmax(ans, r - l); // 最后再更新一次最长子串的长度

    return ans; // 返回结果
}

9.找到字符串中所有字母异位词

题目描述

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

思路：滑动窗口+字符频率统计

  1. 滑动窗口：
    • 使用一个固定大小的窗口（大小为 p 的长度）在 s 上滑动。
    • 每次滑动窗口时，检查窗口内的字符频率是否与 p 的字符频率匹配。
  2. 字符频率统计：
    • 使用两个数组 flagp 和 flags 分别记录 p 和当前窗口的字符频率。
    • 通过比较 flagp 和 flags，判断当前窗口是否是 p 的字母异位词。
  3. 滑动窗口更新：
    • 每次滑动窗口时，移除左边界字符的频率，并添加右边界字符的频率。
    • 检查更新后的 flags 是否与 flagp 匹配。

code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int* findAnagrams(char* s, char* p, int* returnSize) {
    int m = strlen(s); // 字符串 s 的长度
    int n = strlen(p); // 字符串 p 的长度
    *returnSize = 0; // 初始化返回结果的数量

    // 如果 s 的长度小于 p 的长度，直接返回 NULL
    if (m < n) return NULL;

    // 统计 p 中每个字符的频率
    int flagp[26];
    memset(flagp, 0, sizeof(flagp)); // 初始化 flagp 数组为 0
    for (int i = 0; i < n; i++) {
        flagp[p[i] - 'a']++; // 统计 p 中每个字符的频率
    }

    // 动态分配结果数组
    int* ans = malloc(sizeof(int) * (m - n + 1));

    // 统计 s 中前 n 个字符的频率
    int flags[26];
    memset(flags, 0, sizeof(flags)); // 初始化 flags 数组为 0
    for (int i = 0; i < n; i++) {
        flags[s[i] - 'a']++; // 统计 s 中前 n 个字符的频率
    }

    // 检查初始窗口是否与 p 的字符频率匹配
    bool flag = true;
    for (int i = 0; i < 26; i++) {
        if (flags[i] != flagp[i]) {
            flag = false; // 如果不匹配，设置 flag 为 false
            break;
        }
    }
    // 如果匹配，将初始窗口的起始索引加入结果数组
    if (flag) ans[(*returnSize)++] = 0;

    // 滑动窗口
    for (int i = 1; i < m - n + 1; i++) {
        // 移除左边界字符的频率
        flags[s[i - 1] - 'a']--;
        // 添加右边界字符的频率
        flags[s[i + n - 1] - 'a']++;

        // 检查当前窗口是否与 p 的字符频率匹配
        flag = true;
        for (int j = 0; j < 26; j++) {
            if (flags[j] != flagp[j]) {
                flag = false; // 如果不匹配，设置 flag 为 false
                break;
            }
        }
        // 如果匹配，将当前窗口的起始索引加入结果数组
        if (flag) ans[(*returnSize)++] = i;
    }

    return ans; // 返回结果数组
}

10.和为K的子数组

题目描述

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

思路：哈希表+前缀和

  1. 前缀和：
    • 定义前缀和 sum[i] 表示从数组开头到第 i 个元素的累加和。
    • 任意子数组 nums[j..i] 的和可以表示为 sum[i] - sum[j-1]。
  2. 问题转化：
    • 我们需要找到满足 sum[i] - sum[j] = k 的 i 和 j。
    • 这等价于找到满足 sum[j] = sum[i] - k 的 j。
  3. 哈希表优化：
    • 使用哈希表记录前缀和 sum[j] 出现的次数。
    • 遍历数组时，计算当前前缀和 sum[i]，并检查哈希表中是否存在 sum[i] - k。
    • 如果存在，则说明存在若干个子数组满足条件。

code Ⅰ(数组模拟哈希)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int subarraySum(int* nums, int numsSize, int k) {
    if (numsSize == 0) return 0; // 如果数组为空，直接返回 0

    int ans = 0; // 记录符合条件的子数组数量
    int sum = 0; // 记录当前的前缀和

    // 使用哈希表记录前缀和出现的次数
    // 由于 C 语言没有内置的哈希表，这里使用一个简单的数组模拟哈希表
    // 假设 sum 的范围在 -10^7 到 10^7 之间
    int hash[20000001] = {0}; // 哈希表大小为 20000001，偏移量为 10000000
    int offset = 10000000; // 偏移量，用于处理负数

    // 初始化哈希表
    hash[0 + offset] = 1; // 前缀和为 0 的情况出现一次

    // 遍历数组
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i]; // 计算当前的前缀和

        // 检查是否存在前缀和等于 sum - k
        if (hash[sum - k + offset] > 0) {
            ans += hash[sum - k + offset]; // 更新结果
        }

        // 更新当前前缀和的哈希表
        hash[sum + offset]++;
    }

    return ans; // 返回结果
}

code Ⅱ

#include <stdio.h>
#include <stdlib.h>

// 定义哈希表节点结构体
typedef struct {
    int prefixSum; // 前缀和
    int count;     // 该前缀和出现的次数
    UT_hash_handle hh; // uthash 所需的句柄
} HashNode;

int subarraySum(int* nums, int numsSize, int k) {
    if (nums == NULL || numsSize == 0) return 0; // 如果数组为空，直接返回 0

    HashNode* hashtable = NULL; // 初始化哈希表
    int result = 0; // 记录符合条件的子数组数量
    int prefixSum = 0; // 记录当前的前缀和

    // 插入初始节点 {prefixSum: 0, count: 1}
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->prefixSum = prefixSum;
    node->count = 1;
    HASH_ADD_INT(hashtable, prefixSum, node); // 将节点插入哈希表

    // 遍历数组
    for (int i = 0; i < numsSize; i++) {
        prefixSum += nums[i]; // 计算当前的前缀和

        // 检查哈希表中是否存在 prefixSum - k
        int remaining = prefixSum - k;
        HASH_FIND_INT(hashtable, &remaining, node);
        if (node != NULL) {
            result += node->count; // 如果存在，累加对应的 count
        }

        // 更新哈希表
        HASH_FIND_INT(hashtable, &prefixSum, node);
        if (node != NULL) {
            node->count++; // 如果当前前缀和已存在，增加其 count
        } else {
            // 如果当前前缀和不存在，插入新节点
            node = (HashNode*)malloc(sizeof(HashNode));
            node->prefixSum = prefixSum;
            node->count = 1;
            HASH_ADD_INT(hashtable, prefixSum, node);
        }
    }

    // 释放哈希表内存
    HashNode *current, *tmp;
    HASH_ITER(hh, hashtable, current, tmp) {
        HASH_DEL(hashtable, current); // 从哈希表中删除节点
        free(current); // 释放节点内存
    }

    return result; // 返回结果
}

http://www.niftyadmin.cn/n/5863363.html

相关文章

编程考古-忘掉它，Delphi 8 for the Microsoft .NET Framework

编程考古-忘掉它，Delphi 8 for the Microsoft .NET Framework

忘掉它吧&#xff0c;作一篇记录&#xff01; 【圣何塞&#xff0c;加利福尼亚 – 2003年11月3日】在今日的Borland开发者大会上&#xff0c;Borland正式推出了Delphi 8 for Microsoft .NET Framework。这款新版本旨在为Delphi开发者提供一个无缝迁移路径&#xff0c;将现有的…
阅读更多...
c++贪心系列

c++贪心系列

各位小伙伴们新年好呀&#xff0c;这是年后的第一篇文章&#xff0c;那么还是一样&#xff0c;我们继续学习这个贪心算法。 第一题 题目链接 2418. 按身高排序 - 力扣&#xff08;LeetCode&#xff09; 题目解析 代码原理 方法一 1.先创建一个下标数组&#xff0c;将两个数…
阅读更多...
算法很美笔记（Java）——动态规划

算法很美笔记（Java）——动态规划

解重叠子问题&#xff08;当前解用到了以前求过的解&#xff09; 形式&#xff1a;记忆型递归或递推&#xff08;dp&#xff09; 动态规划本质是递推&#xff0c;核心是找到状态转移的方式&#xff0c;也就是填excel表时的逻辑&#xff08;填的方式&#xff09;&#xff0c;而…
阅读更多...
[MDM 2024]Spatial-Temporal Large Language Model for Traffic Prediction

[MDM 2024]Spatial-Temporal Large Language Model for Traffic Prediction

论文网址&#xff1a;[2401.10134] Spatial-Temporal Large Language Model for Traffic Prediction 论文代码&#xff1a;GitHub - ChenxiLiu-HNU/ST-LLM: Official implementation of the paper "Spatial-Temporal Large Language Model for Traffic Prediction" …
阅读更多...
3damx 发动机活塞运动动画

3damx 发动机活塞运动动画

使用HD解算器绑定&#xff1a;点(绑定的最终目标对象)→曲柄→活塞&#xff08;子控父&#xff0c;反向解算&#xff09; 点:绑定到轮子上的连接点
阅读更多...
C语言：什么是动态内存管理？

C语言：什么是动态内存管理？

动态内存管理是指在程序运行期间&#xff0c;根据实际需要动态地分配和释放内存空间的过程。与静态内存分配在编译时就确定内存大小不同&#xff0c;动态内存管理允许程序在运行时根据具体情况灵活地申请和释放内存。 主要通过 malloc 、 calloc 、 realloc 和 free 函数来实现…
阅读更多...
04-DevOps-安装并初始化Jenkins

04-DevOps-安装并初始化Jenkins

Jenkins由Java语言开发&#xff0c;用于监控持续重复的工作&#xff0c;包括&#xff1a;持续的软件版本发布/测试项目&#xff0c;监控外部调用执行的工作。 Jenkins主要起到一个驱动者&#xff0c;流水线的工作&#xff0c;下游代码拉取&#xff0c;上游生产环境发布、构建&…
阅读更多...
PHP2（WEB）

PHP2（WEB）

##解题思路 打开页面什么线索都没有&#xff0c;目录扫描只是扫出来一个index.php&#xff0c;而源代码没有东西&#xff0c;且/robots.txt是不允许访问的 于是一番查询后发现&#xff0c;有个index.phps的文件路径&#xff0c;里头写着一段php的逻辑&#xff0c;对url的id参数…
阅读更多...
最新文章

Copyright @ 2022~2023