代码随想录算法训练营第六天 | 242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

242. 有效的字母异位词

哈希表有最大长度26，直接使用数组做哈希。

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0 for i in range(26)]

        for char in s:
            record[ord(char)-ord('a')] += 1
        for char in t:
            record[ord(char)-ord('a')] -= 1
        
        return not any(record)

349. 两个数组的交集

这题python其实很好AC一行就可以了..

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

学一下别人的写法：

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        return self.set_intersection(set1, set2)

    def set_intersection(self, set1, set2):
        if len(set1) > len(set2):
            return self.set_intersection(set2, set1)
        return [x for x in set1 if x in set2]

定义交集函数让set1总是更小的可以优化性能。

202. 快乐数

 建一个集合用于记录目前为止的各位平方和，如果等于1说明是快乐数，否则一旦发现重复了直接报告Flase.

class Solution:
    def isHappy(self, n: int) -> bool:
        record = set()

        while True:
            record.add(n)
            n = sum([int(x) ** 2 for x in str(n)])
            if n == 1:
                return True
            if n in record:
                return False

1. 两数之和

每次做这一题都需要打开评论查看一下"有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。"

言归正传，建一个哈希表，key放数值，value放对应的索引。每次循环查target-num键是否在哈希表中，如果在报告结果。否则把当前num存入哈希表，值为对应的索引。

from collections import defaultdict
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = defaultdict(int)
        for i,num in enumerate(nums):
            if target - num in record:
                return [i, record[target - num]]
            record[num] = i
        return []
            

这里再写一个双指针实现，为后续的三数之和、四数之和做准备。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sorted_nums = sorted(nums)
        left, right = 0, len(nums) - 1
        while left < right:
            if sorted_nums[left] + sorted_nums[right] == target:
                left_index = nums.index(sorted_nums[left])
                right_index =  nums.index(sorted_nums[right])
                return [left_index, nums[left_index + 1:].index(sorted_nums[left]) + left_index + 1] if sorted_nums[left] == sorted_nums[right] else [left_index, right_index]
            elif sorted_nums[left] + sorted_nums[right] < target:
                left += 1
            else:
                right -= 1