1.两个数组的交集
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
class Solution: def intersect(nums1, nums2) : hashMap=collections.defaultdict(int) res=[] for i in range(len(nums1)): hashMap[nums1[i]]+=1 for i in range(len(nums2)): if hashMap[nums2[i]]!=0: res.append(nums2[i]) hashMap[nums2[i]]-=1 return res
2.两个数的交集Ⅱ
给你两个整数数组
nums1和nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
def intersect(nums1, nums2): hashMap=collections.defaultdict(int) res=[] for i in range(len(nums1)): hashMap[nums1[i]]+=1 for i in range(len(nums2)): if hashMap[nums2[i]]!=0: res.append(nums2[i]) hashMap[nums2[i]]-=1 return res
3.快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
def getSum(n): nums=0 while n: nums+=(n%10)**2 n=n//10 return nums def isHappyNumber(n): s=set() n=getSum(n): while n: if n==1: return True if n in mid: return False else: s.add(n)
4.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
(1)暴力解法
循环遍历时间复杂度为O(n^2)
def getSum(nums,target): for i in range(len(nums)): for i in range(i+1,len(nums)): if nums[i]+nums[j]==target: return [i,j]
(2)使用集合，时间复杂度为O(n)
def getSum(nums,target): #创建一个集合来存储我们目前看到的数字 seen = set() for i, num in enumerate(nums): complement = target - num if complement in seen: return [nums.index(complement), i] seen.add(num)
5.四数相加
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
- 0 <= i, j, k, l < n
- nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1：
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
1.暴力解法
这道题用暴力时间复杂度较大，为O(n^4)
def fourSumCount(nums1, nums2, nums3 nums4): res = 0 for i in range(len(nums1)): for j in range(len(nums2)): for k in range(len(nums3)): for h in range(len(nums4)): if nums1[i]+nums2[j]+nums3[k]+nums4[h]==0: res+=1 return res
2. 使用哈希表，该题与两数之和有点类似
def fourSumCount(nums1, nums2, nums3, nums4) hashMap=collections.defaultdict(int) for i in range(len(nums1)): for j in range(len(nums2)): hashMap[nums1[i]+nums2[j]]+=1 res=0 for i in range(len(nums3)): for j in range(len(nums4)): if hashMap[0-nums3[i]-nums4[j]] !=0: res+=hashMap.get(0-nums3[i]-nums4[j]) return res
