完整网站设计,免费logo图标在线制作 设计,电商运营网站,公司注册地址和办公地址不一样前缀和
1. 560. 和为 K 的子数组
中等
给你一个整数数组 nums 和一个整数 k #xff0c;请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1#xff1a;
输入#xff1a;nums [1,1,1], k 2
输出#xff1a;2示例 2#…前缀和
1. 560. 和为 K 的子数组
中等
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1
输入nums [1,1,1], k 2
输出2示例 2
输入nums [1,2,3], k 3
输出2
提示
1 nums.length 2 * 104-1000 nums[i] 1000-107 k 107 class Solution { public: int subarraySum(vectorint nums, int k) { int n nums.size(); // 获取输入数组的大小 unordered_mapint,int unMap; // 哈希表用来存储前缀和的频次 unMap[0] 1; // 初始化哈希表表示前缀和为0出现1次这对从索引0开始的子数组非常重要 vectorint pre(n1); // 存储前缀和的数组pre[i] 表示 nums[0] 到 nums[i-1] 的和 int result{}; // 用于存储满足条件的子数组个数 for(int i 0; i n; i) { pre[i1] pre[i] nums[i]; // 更新当前的前缀和 // 判断当前前缀和减去 k 是否存在于哈希表中 if(unMap.find(pre[i1] - k) ! unMap.end()) { // 如果存在说明从之前某个位置到当前的位置的子数组和为 k result unMap[pre[i1] - k]; // 将该频次累加到结果中 } // 更新当前前缀和的频次 unMap[pre[i1]]; } return result; // 返回满足条件的子数组个数 } }; 解释:
per[i1] 表示从 nums[0] 到 nums[i] 的累加和。
子数组 nums[0..i] 的和可以通过公式计算 sum(nums[0..i])per[i1]−per[0]
前缀树
1. 208. 实现 Trie (前缀树)
中等
Trie发音类似 try或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补全和拼写检查。
请你实现 Trie 类
Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中返回 true即在检索之前已经插入否则返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix 返回 true 否则返回 false 。
示例
输入
[Trie, insert, search, search, startsWith, insert, search]
[[], [apple], [apple], [app], [app], [app], [app]]
输出
[null, null, true, false, true, null, true]解释
Trie trie new Trie();
trie.insert(apple);
trie.search(apple); // 返回 True
trie.search(app); // 返回 False
trie.startsWith(app); // 返回 True
trie.insert(app);
trie.search(app); // 返回 True // 字典树Trie的实现 class Trie { private: // 子节点数组存储当前节点的所有子节点26个字母 vectorTrie* children; // 标记当前节点是否是某个单词的结束 bool isEnd; // 辅助函数查找指定前缀的最后一个节点 Trie* searchPrefix(string prefix) { Trie* node this; // 从当前节点根节点开始查找 for (char ch : prefix) { // 遍历前缀字符串的每个字符 ch - a; // 将字符转换为索引值a 对应索引 0z 对应索引 25 if (node-children[ch] nullptr) { // 如果对应的子节点不存在 return nullptr; // 前缀不存在返回空指针 } node node-children[ch]; // 移动到子节点 } return node; // 返回前缀的最后一个节点 } public: // 构造函数初始化根节点 Trie() : children(26), isEnd(false) {} // 插入一个单词到字典树 void insert(string word) { Trie* node this; // 从根节点开始插入 for (char ch : word) { // 遍历单词的每个字符 ch - a; // 将字符转换为索引 if (node-children[ch] nullptr) { // 如果对应的子节点不存在 node-children[ch] new Trie(); // 创建一个新的子节点 } node node-children[ch]; // 移动到子节点 } node-isEnd true; // 标记该节点为单词的结束 } // 搜索一个完整单词是否存在于字典树中 bool search(string word) { Trie* node this-searchPrefix(word); // 查找单词的最后一个节点 return node ! nullptr node-isEnd; // 节点存在且是单词结尾 } // 判断是否存在以指定前缀开头的字符串 bool startsWith(string prefix) { return this-searchPrefix(prefix) ! nullptr; // 查找前缀是否存在 } };
