type
status
date
slug
summary
tags
category
icon
password
题目
217. 存在重复元素 - 力扣（LeetCode）
题目：给你一个整数数组
nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。示例 1：
输入：nums = [1,2,3,1] 输出：true
示例 2：
输入：nums = [1,2,3,4] 输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2] 输出：true
提示：
1 <= nums.length <= 105
109 <= nums[i] <= 109
暴力法
- 示例1举例，首先我用1跟之后的元素比较，如果相等我可以count+1操作，只要count≥2就可以输出True，之后再用2遍历，同理……那么比较的时间复杂度是
O(n^2)，空间复杂度是O(1)
排序法
- 在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。
- 时间复杂度：首先排序的时间复杂度是：
O(nlogn),我们只需要遍历一遍所有，时间复杂度为O(n)，所以时间复杂度是O(nlogn)+O(n)，取最大项，所以时间复杂度为O(nlogn)
- 空间复杂度就是
O(1)
哈希表法
- 对于数组中每个元素，我们将它插入到哈希表中。
- 如果插入一个元素时发现该元素已经存在于哈希表中，则不会再插入
- 最后比较哈希表元素个数，如果小于数组元素个数，则一定存在重复元素。
- 时间复杂度是
O(n)，插入n个数
- 空间复杂度是
O(n)，哈希表的开销
242. 有效的字母异位词 - 力扣（LeetCode）
题目：给定两个字符串
s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若
s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。示例 1:
输入:s = "anagram",t = "nagaram" 输出: true
示例 2:
输入:s = "rat",t = "car" 输出:false
提示:
1 <= s.length, t.length <= 5 * 104
s和t仅包含小写字母
数组法
- 我发现因为这个题中只有小写字母，所以一共就可能出现26种英文字母，所以我们可以建立一个26容量的数组，用于存放出现的次数，然后数组的index可以是
’n’-‘a’的值 - 首先先看一下长度大小这个可以直接判断
- 先遍历s增加数组值，再遍历t减少数组值
- 最后遍历数组如果全为0，那么返回true
- 时间复杂度：
O(n)，其中 n 为 s 的长度。
- 空间复杂度：
O(S)，其中 S 为字符集大小，此处 S=26
哈希表法
- 这里用了unordered_map，十分方便的插入键值对
- 思路与暴力法差不多（思路看暴力法就可以）
- 时间复杂度：
O(n)，其中 n 为 s 的长度。
- 空间复杂度：
O(n)，其中 n 为 s 的长度。
排序法（巧妙）
- 我们如果把两个串按照字母的顺序，那么两个串应该一模一样才满足题的条件，这样的做法非常的巧妙
- 时间复杂度：
O(nlogn)，其中 n 为 s 的长度。 - 排序的时间复杂度为
O(nlogn) - 比较两个字符串是否相等时间复杂度为
O(n) - 总体时间复杂度为级数更大的
O(nlogn)
- 空间复杂度：
O(1)
讲解视频：
1. 两数之和 - 力扣（LeetCode）
题目：给定一个整数数组
nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 104
109 <= nums[i] <= 109
109 <= target <= 109
- 只会存在一个有效答案
暴力法
- 我直接两层循环，第一层i:0→n-1，第二层j:i+1→n-1，每次计算出来和是否等于
target即可，非常简单
- 时间复杂度：
O(n^2)
- 空间复杂度：
O(1)
哈希表法
- 我这里使用的是
unordered_map，我的思路是我们这个题是要返回index的，所以这里用unordered_set并不合适，所以我们的value是index，我们的键值对中的key就是数组本身的值，那我们每次循环第i个值是，就看是否能找到另一个值满足和为target，这里就查询一下哈希表里的键值对的key有没有那个值就可以，这里就用到了end()函数(这里的end指的是最后一对的之后部分)，如果到最后还没有就说明没有那个我们想要的值，如果有，就返回那个key的value也就是第二个属性index和本身的index即可！
- 时间复杂度：
O(n)，其中 n 是数组中的元素数量。 - 这里外层循环的时间复杂度是
O(n) - 哈希表的查找的时间复杂度可达到
O(1) - 两者取最高级是
O(n)
- 空间复杂度：
O(n)，其中 n 是数组中的元素数量。 - 这里主要是哈希表的开销
讲解视频：
49. 字母异位词分组
题目：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs =["eat", "tea", "tan", "ate", "nat", "bat"]输出:[["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs =[""]输出:[[""]]
示例 3:
输入: strs =["a"]输出:[["a"]]
提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i]仅包含小写字母
排序法+哈希表存储
- 我们可以把所有串内按照a→z的方式排序，当且仅当它们的排序字符串相等时，两个字符串是字母异位词。
- 比如第一个例子：
- strs =["eat", "tea", "tan", "ate", "nat", "bat"]
- strs =["aet", "aet", "ant", "aet", "ant", "abt"]
- 这里会发现
- ”aet”→[”eat”,”tea”,”ate”],”ant”→[”tan”,”nat”],”abt”→[”bat”]
- 那我们其实这个时候就会想到哈希表
unordered_map的使用了 - key→”aet”,”ant”,”abt”
- 数据类型应该是:
string - value就是["ate","eat","tea"]，["nat","tan"],["bat"]
- 数据类型应该是:
vector<vector<string>> - 所以哈希表的类型应该是
<string, vector<string>>
- 时间复杂度：
O(nklogk)，其中n是strs中的字符串的数量，k是strs中的字符串的的平均长度。 - 需要遍历n个字符串，需要
O(n)的时间 - 对于每个字符串，需要
O(klogk)的时间进行排序 - 更新哈希表需要
O(1)的时间 - 所以总共
O(nklogk)的时间
- 空间复杂度：
O(nk)，其中n是strs中的字符串的数量，k是strs中的字符串的的平均长度。需要用哈希表存储全部字符串。
计数+哈希表存储
- 其实这个题在经历前面的题之后很容易想到用
ASCII码的差来作为哈希表的key，但是经过思考发现这并不可行，无法将相同构造的串统一成一个串作为key
- 这个时候我发现如果我们用26位的串作为
key或许可行，遍历每一个串如果每个字母出现的次数相同，整个串相同，可以作为key！！ - 比如第一个例子：
- strs =["eat", "tea", "tan", "ate", "nat", "bat"]
- strs =["10001000000000000001000000", "10001000000000000001000000", "10000000000001000001000000", "10001000000000000001000000", "10000000000001000001000000", "11000000000000000001000000"]
- 之后和上面是一样的了不再赘述了，所以代码只有上半部分改变
- 时间复杂度：
O(nk)，其中n是strs中的字符串的数量，k是strs中的字符串的的平均长度。 - 需要遍历n个字符串，需要
O(n)的时间 - 每个字符串平均为k个字符，遍历需要
O(k)的时间 - 更新哈希表需要
O(1)的时间 - 所以总共
O(nk)的时间
- 空间复杂度：
O(nk)，其中n是strs中的字符串的数量，k是strs中的字符串的的平均长度。需要用哈希表存储全部字符串。
讲解视频：
📎 参考文章
- 题目来源
- 引用视频
- 引用文章
- Author:Chailyn
- URL:https://own.chailyncui.blog/article/%E5%93%88%E5%B8%8C%E8%A1%A8-3
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!