商城网站建设的注意事项电商平台有哪些

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;  // 直接返回}}}// 如果没有找到答案，释放内存并返回 NULLfree(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++) {// 分配内存并初始化字符频率统计数组 tint *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; // 如果不匹配，标记为 falsebreak;}}// 如果找到匹配的分组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(nlogn)$。
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) {// 如果数组为空，直接返回 0if (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];}}// 将剩余的位置填充为 0while (j < numsSize) {nums[j++] = 0;}
}

5.盛最多水的容器

题目描述

11. 盛最多水的容器

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

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

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

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

示例 1：

输入：[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 - 2if (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：

输入：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 个，因此数组大小为 128bool 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 的长度，直接返回 NULLif (m < n) return NULL;// 统计 p 中每个字符的频率int flagp[26];memset(flagp, 0, sizeof(flagp)); // 初始化 flagp 数组为 0for (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 数组为 0for (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 为 falsebreak;}}// 如果匹配，将初始窗口的起始索引加入结果数组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 为 falsebreak;}}// 如果匹配，将当前窗口的起始索引加入结果数组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; // 如果数组为空，直接返回 0int ans = 0; // 记录符合条件的子数组数量int sum = 0; // 记录当前的前缀和// 使用哈希表记录前缀和出现的次数// 由于 C 语言没有内置的哈希表，这里使用一个简单的数组模拟哈希表// 假设 sum 的范围在 -10^7 到 10^7 之间int hash[20000001] = {0}; // 哈希表大小为 20000001，偏移量为 10000000int offset = 10000000; // 偏移量，用于处理负数// 初始化哈希表hash[0 + offset] = 1; // 前缀和为 0 的情况出现一次// 遍历数组for (int i = 0; i < numsSize; i++) {sum += nums[i]; // 计算当前的前缀和// 检查是否存在前缀和等于 sum - kif (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; // 如果数组为空，直接返回 0HashNode* 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 - kint 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; // 返回结果
}