参考文献 代码随想录
一、有效的字母异位词
给定两个字符串 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 * 104s和t仅包含小写字母
解法1：在python中使用统计某个字符，然后在判断与另外一个列表中的字符是否相等，需要注意的是，它们的长度必须相等，如果不想等的话，那么久返回False，一下这个方法仅供参考，因为本人也没有通过（超时）超时的原因：就是你每次都要寻找一次，有写字母已经判断过了，但是这个思路仍然需要进行统计字符出现的次数，而且统计字母次数的时间复杂度为O（n），所以就超时了
class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ # 可以把它们转化为列表的形式，然后在统计每个字母的次数是否已与另外一个字符列表相等(两个字符列表相等的情况下，还有不相等的情况，那肯定就返回False) sList = list(s) tList = list(t) if len(sList) != len(tList): return False for char in sList: if sList.count(char) != tList.count(char): return False return True
解法二：通过字典来计数，先统计提一个字符串中每个字符出现的次数，然后，在根据另外一个字符串中每个字母出现，来--，如果，对应的值都为0，说明，两个字符串中每个字母出现的次数刚好相等，否则，要么一个字符的字母多了，或者少了。
class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ # 定义一个列表，存放的是每个字母出现的个数，然后初始值都为0，先遍历一个列表，左++，另外一个列表做--，如果定义的这个列表中出现了不是为0的说明，要么一个列表多了，要么少了 indexList = [0] * 26 for i in s: # 先统计s这个字符串每个字母出现的次数 indexList[ord(i) - ord("a")] += 1 for i in t: # 遍历t上一个字符串中每个字母出现的次数做--，操作，如果为零，说明s,和，t的每个字符出现的次数同一样 indexList[ord(i) - ord("a")] -= 1 for i in indexList: if i != 0: return False return True
二、两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的
提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
解法1：判断第一个数组里面的元素是否在另外一数组里面，如果存在，那么就添加到另外一临时数组里，否则什么也不做操作。
class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ aid = [] for i in nums1: if i in nums2: aid.append(i) return list(set(aid))
解法二：使用集合，求交集即可
class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ a = set(nums1) b = set(nums2) return list(a & b)
解法三：使用2个数组，分别存储每个列表中的元素，如果两个列表对应的值大于1，说明了，是交集
class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ aid1 = [0] * 1001 aid2 = [0] * 1001 for i in nums1: aid1[i] += 1 for j in nums2: aid2[j] += 1 r = [] for i in range(1001): if aid1[i] * aid2[i] > 0: r.append(i) return r
三、快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
示例 2：
输入：n = 2 输出：false
提示：
1 <= n <= 231 - 1
问题分析：首先要考虑的是，如何防止死循环，可以使用一个列表来存储，如果它出现了2次说明已经死循环，就可以调出了，否则就添加到列表中，然后统计每个各位上平方之和，在判断是否为1，如果不是那么就要跟新到n的值
class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ record = [] # 为了下面的判断，不要陷入死循环 while n not in record: record.append(n) # 把这个数添加到列表中，防止死循环 num_sum = 0 # 记录每次数的各个位上平方之和 n_str = str(n) for i in n_str: num_sum += int(i) ** 2 if num_sum == 1: # 如果各个位上平方之和 == 1说明已经找到了 return True else: # 否则跟新n n = num_sum return False
四、两数之和
给定一个整数数组 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- 只会存在一个有效答案
问题分析：我们可以把当前遍历的数添加到一个数组或者是字典里，然后在循环里，先判断目标数-当前循环的元素是否在之前的数组或者是字典里，如果在那么返回对应的下标，如果不在，则返回空数组
数组版本：
在Python中，对于频繁的数据访问操作，数组（通常指列表，即list类型）和字典（dict类型）的效率差别不大。数组的访问时间复杂度是O(1)，而字典的平均时间复杂度是O(1)，看起来似乎都是常数级别的时间复杂度。
但在特定情况下，数组和字典的表现可能会有明显差异：
-
数组（列表）：适合当你需要通过索引来快速访问元素，或者在列表末尾频繁添加或删除元素。
-
字典：适合当你需要通过键来快速访问元素，并且不关心元素的顺序或者它们的添加/删除频率。
如果你需要频繁地通过键来访问元素，并且不需要关心元素的顺序，使用字典会更高效。
如果你需要保持元素的插入顺序，并且需要通过索引来频繁访问元素，或者你需要在列表的任意位置频繁插入和删除元素，使用数组（列表）会更高效。
在实际应用中，除非有极端的性能需求，否则通常不需要过度关注哪个更高效，而是根据需求选择合适的数据结构
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ # 使用的是数组 li = [100000000000000] * 100000 for index, value in enumerate(nums): if target - value in li: # 就是用目标值减去当前遍历的值，然后在判断剩下的部分是否在之前的字典中 return [li.index(target - value), index] li[index] = value return []
字典版本：
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ # 使用的是字典 aid = {} for index, value in enumerate(nums): if target - value in aid: # 就是用目标值减去当前遍历的值，然后在判断剩下的部分是否在之前的字典中 return [aid[target - value], index] aid[value] = index return []为什么不写aid[index] = value呢？因为当你查找剩下的数的下标的时候不知道，这时你就知道当前元素的下标而已，但你不知道剩下元素的下标是多少，也可以使用其它方法来寻找，但是这些方法不常用
