242. Valid Anagram

这题有好几种解法，首先我自己想的

1
2
3
4
5
6
7
8
s_set, t_set = set(s),set(t)
if len(s_set) != len(t_set):
    return False
merged_set = s_set | t_set
if len(merged_set) == len(s_set) and len(merged_set) == len(t_set):
    return True
else:
    return False

有问题，因为set（）没法判断长度是否相等，比如aabb和ab最后会返回true

最简单高效的方法是引入collections包里的Counter方法，Counter方法主要统计 （）中每个字符的出现次数，所以只需要判断结果是否相等即可

还有就是sorted（）方法，可以将字符从a到z按顺序排列，也就是说如果排序好的s和t长度和字母都一样就说明是true

核心思路还是统计每个字符串里单词出现的次数，所以可以按照Counter的思路，设计1个dict储存s出现的字符和次数，key对应字符，value对应次数，然后再遍历t，然后找到出现的字符，将其对应的value-1，最后再判断一次dict里面的所有value是否为0，如果不是则返回false：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):  # 长度不同，直接返回 False
        return False

    char_count = {}  # 创建字典存储 s 中字符的出现次数

    # 统计 s 中每个字符的频率
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1  # 若 char 不在字典中，则默认为 0，再 +1

    # 遍历 t，减少对应字符的次数
    for char in t:
        if char not in char_count or char_count[char] == 0:  # 如果 t 中的字符不在 s 中，或次数为 0
            return False
        char_count[char] -= 1  # 减少对应字符的出现次数

    # 检查字典中是否所有值都为 0（其实不检查也可以，因为长度相等 + 上面操作确保匹配）
    return all(value == 0 for value in char_count.values())

349. Intersection of Two Arrays

这里主要注意并集和交集的符号使用

两个集合set取并集set(s1) | set(s2),取交集 set(s1) & set(s2)

还有注意python中的set和dict底层结构都是哈希表，最主要的区别是set没有值，dict有key-value

202. Happy Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def isHappy(self, n):
    """
    :type n: int
    :rtype: bool
    """
    if n <= 9 and n != 1: # 不需要判断是否为1，循环里也能判断，如果是1的话平方还是自己，最后会返回True
        return False
    if n == 1:
        return True

    # 首先可以通过将给定的n转换为字符然后快速得到每个数字,这里用map()最快
    nums = list(map(int,str(n)))
    sum_ = 0
    seen = set()
    while True:
        sum_ = 0

        for num in nums:
            sum_ += num ** 2

        if sum_ == 1: 
            return True
        if sum_ < 10 and sum_ != 1: # -----这里有问题。小于10也可以是快乐书，只是平方就是它本身，不需要加其他数，比如7
            return False
        if sum_ in seen:
            return False

        seen.add(sum_)
        nums = list(map(int,str(sum_)))

又是错的，个位数也是快乐数！不能忽视！

核心思想就是将sum_放到set里，去重，同时再判断新的sum有没有在set里，有的话就是死循环，返回false，没有就继续，直到变成1或者死循环。

第二点就是会得到任意n的所有组成数字，使用nums = list(map(int,str(n)))，还有其他方法， 比较简单的就是将n转换为字符串，然后再通过遍历或者拆分得到每一个字符，再将字符转换为数字就可以了，上面这里就是先转换为str，然后通过map将每个str转换为int，最后再变成list。

还有一种方法就是，主要判断循环是否跳出的条件就是最后是1还是死循环，而死循环可以通过弗洛伊德算法判断是否有环，也就是定义两个快慢指针，快的要是和慢的能走到一起那就是死循环，如果快的先到1那就不是

1. Two Sum

目前只用了暴力解法，并且可以进一步优化：

1
2
j = idx + 1
while j <= len(nums)-1:

这里可以合并成

1
2
for j in range(idx+1, len(nums)):
等于for(j=i+1;j<nums.size()-1;)

第二种思路：用字典，字典是哈希表的一种，可以通过 key = num_dict[value]找到值对应的索引，也可以通过索引找值 value = num_dict[key]，所以我们只需要遍历nums，然后将target分别减去每一个数，如果得到的结果可以在字典中找到，那就返回字典中找到的值的索引和遍历到当前值的索引，如果没有找到那就往字典里添加当前的值和对应的当前的索引。

454. 4Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def fourSumCount(self, nums1, nums2, nums3, nums4):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :type nums3: List[int]
    :type nums4: List[int]
    :rtype: int
    """
    sum_12 = defaultdict(list)
    sum_34 = defaultdict(list)

    for i in range(len(nums1)):
        for j in range(len(nums2)):
            num = nums1[i] + nums2[j]
            sum_12[num] = [i, j] # ++而不是赋值索引

    for k in range(len(nums1)):
        for l in range(len(nums2)):
            num = nums3[k] + nums4[l]
            sum_34[num] = [k, l] # ++而不是赋值索引

    counter = 0
    for i in sum_12:
        for j in sum_34:
            if i + j == 0:
                counter += 1 #需要计算次数后相乘

    return counter

这题的思路就是拆分为两个两个数之和。最后是n^2的复杂度，比暴力n^4好

但是上面的代码有几个问题，首先是我们不需要记住具体的索引是多少，只需要统计符合条件的结果有几个。因此我们只需要定义：

1
2
sum_12 = defaultdict(int)
sum_34 = defaultdict(int)

即可，计算出两个数之和得到答案的次数，

sum_12[num] = 3，即 A[i] + B[j] = num 的情况出现了 3 次。

sum_34[-num] = 4，即 C[k] + D[l] = -num 的情况出现了 4 次。

对于这 3 种 (A[i], B[j]) 组合，每种都可以搭配 4 种 (C[k], D[l]) 组合：总共的匹配情况=3×4=12

所以我们在最后通过乘法来算出所有情况，而不是上面的简单加1，当然最后可以优化成a+(-a)=0，从而减少一次for循环

1
2
3
for num in sum_12:
        if -num in sum_34:  # 查找是否存在 -(A+B) == (C+D)
            counter += sum_12[num] * sum_34[-num]  # 计算总匹配次数

383. Ransom Note

这题做对了，但是还可以再优化一下代码，核心思想就是创建一个字典用于存放magazine的所有字符出现的次数，然后再遍历ransomNote，将匹配到的字符对应的次数-1，如果出现magazine没有的字符则返回false，并且如果magazine字典里的次数被用完了也就是<=0的时候也返回false。

优化：

1
2
3
4
5
6
7
8
9
10
for j in ransomNote:

    if j not in m_dict: 
        return False

    if j in m_dict:
        if m_dict[j] <= 0:
            return False
        else:
            m_dict[j] -= 1

if j not in m_dict 其实是多余的，因为 defaultdict(int) 默认 0，所以 m_dict[j] 不存在时 m_dict[j] == 0，可以直接判断 if m_dict[j] == 0。

15. 3Sum

这题非常经典，没做出来

解法1：排序+哈希表

首先将nums排序，这样可以使得输出的时候的元组的顺序固定，防止出现顺序不一样元素一样的结果

然后固定第一个数nums[i]，遍历第二个数nums[j]，并通过c = 0-(nums[i]+nums[j])来匹配第三个数

这个时候要注意，由于要求结果不能重复，如果 c 需要在整个 nums 里查找，那 nums[k] 可能比 nums[i] 还小，这样就会出现重复或者无效的解。注意题目要求 i != j, i != k, and j != k。

所以使用seen = set()来保存出现的nums[j]，而nums[j]可以表示为除了nums[i]的其他元素，我们可以将seen.add(nums[j])放在for j的里面，也可以放在for i的里面，两者区别主要是前者动态比较c与两个数的和，确保后面得到的结果不会重复，后者会这样所以需要额外增加去重步骤。

所以我们先判断c是不是在seen里，如果是，就说明nums里面包含了满足条件的三个数，将其添加到结果set res_set里，注意res_set不能直接添加[nums[i] ,nums[j], c], 其会报list不是可哈希的错误。所以我们要添加元组（nums[i] ,nums[j], c）到res_set里，在最后将元组通过map转换成list。

c如果不在seen里那就把nums[j]添加进seen，这样循环到最后会把除了num[i]的其他元素都添加进seen，并且能够按顺序判断得到多个元组。

注意seen 必须使用 set()，不能使用 list()，因为set 查找补数 (complement in seen) 是 O(1)，而 list 查找是 O(N)，会导致算法变慢

解法2：排序+双指针

首先也是排序，这样就能通过双指针来做了，主要是固定第一个数字nums[i]，然后将剩下的list里的最左边和最右边分别用相加，如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

18. 4Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort() # [-2, -1, 0, 0, 1, 2]
        res_set = set()
        for i in range(len(nums)-4):
            for j in range(i+1, len(nums)-3):
                c = nums[i] + nums[j]

                left = j + 1
                right = len(nums) - 1

                while left < right:
                    if c + nums[left] + nums[right] > target:
                        right -= 1
                    elif c + nums[left] + nums[right] < target:
                        left += 1
                    if c + nums[left] + nums[right] == target:
                        res_set.add((nums[i],nums[j],nums[left],nums[right]))
                        left += 1

        return list(map(list,res_set))

上面是我根据提示写出来的代码。提示是和3Sum一样用双指针法，所以我的思路是排序后先将两个数相加，然后再将剩下的数用双指针遍历。

其中有几个错误需要注意。

for循环范围错误：for i in range(len(nums)-4):应该是len(nums)-3， for j in range(i+1, len(nums)-3):应该是len(nums)-2，这是因为range(len(nums) - 4) 意味着 i 只能遍历到 len(nums) - 5，但我们需要 i 取到 len(nums) - 4。同理。

i 和 j没有考虑重复的元素，比如nums[i] ==nums[i-1]的话可能出现重复解,因此在两个for之后都需要判断当前的nums[i]是否和nums[i-1]相等，当然需要有效的i，即i>0，j也需要j > i+1 and nums[j] == nums[j-1]，这个时候需要跳过当前相同的值，比如：

1
2
3
4
5
6
7
nums = [-2, -2, -1, 0, 1, 2, 2, 2]
i = 0, nums[i] = -2
i = 1, nums[i] = -2 # 重复了，需要跳过
如果不加 if i > 0 and nums[i] == nums[i - 1]: continue，那么：
i = 0, nums[i] = -2 会找到所有符合的四元组。
i = 1, nums[i] = -2 会重复计算完全一样的四元组。
最终会出现重复解：[-2, -1, 0, 1] ，[-2, -1, 0, 1] # 计算两次

j也同理。

if c + nums[left] + nums[right] == target:判断错误：如果在前面left或者right变化后，nums[left] + nums[right] 可能已经越界！所以应该是elif或者else而不是if。

最后还有left和right重复的情况没考虑：如果nums[left] == nums[left + 1]或者nums[right] == nums[right - 1]的时候，需要跳过重复解，为什么用while不用if是因为left或者right旁边可能有很多个相同的值，因为已经排序过了。

最后注意双指针的while条件是left += 1和right -= 1同时作用，确保 left 指向新的不同值，right 也指向新的不同值，防止重复匹配相同解。

而对于双指针法的应用，到底是都收缩还是只变一个需要具体问题具体分析。如3，4数之和就需要都变，而滑动窗口求最大子序列就只需要变left等。