454.四数相加II
题目链接：
454. 四数相加 II - 力扣（Leetcode）
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
例如:
输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:2
收获的点
1）Counter函数又用上了
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
#将四个数组转化为索引相同的字典，字典的key为数组的索引，字典的value为四个数组对应的值的列表（或元组），通过查找索引对应的不同数值判断有多少个元组
hashtable = Counter(u+v for u in nums1 for v in nums2) #将第一个数组和第二个数组的和加起来
ans = 0
for i in nums3:
for j in nums4:
if -(i+j) in hashtable:
ans +=hashtable[-i-j] #如果数组3和数组4存在数组1和数组2加和为0的记一次
return ans
- 赎金信
题目链接：
383. 赎金信 - 力扣（Leetcode）
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
#判断ransomNote中的元素都在magazine里面感觉就可以了，即前者是后者的子集
a = Counter(ransomNote)
b = Counter(magazine)
for x in ransomNote:
value = b.get(x)
value2 = a.get(x)
if value is None or int(value) < int(value2):
return False
return True
一道基本自己做出来的题，但是发现还有更简洁的解法：
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
c1 = collections.Counter(ransomNote)
c2 = collections.Counter(magazine)
x = c1 - c2
#x只保留值大于0的符号，当c1里面的符号个数小于c2时，不会被保留
#所以x只保留下了，magazine不能表达的
if(len(x)==0):
return True
else:
return False
三数之和
题目链接：
15. 三数之和 - 力扣（Leetcode）
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
收获的点：
1）对于重复值的去除，第一个元素去重，nums[i]==nums[i-1]的判断；
2）第二个元素和第三个元素在while里面的去重，非常值得回味；
3）索引遍历+双指针的思路。
完整代码：
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
res = []
if nums is None or n < 3:
return []
for i in range(n):
if nums[i] > 0:
return res
if i > 0 and nums[i] == nums[i-1]: #去重第一个元素
continue
L = i + 1
R = n - 1
while L < R :
if nums[i] + nums[L] + nums[R] ==0:
res.append([nums[i],nums[L], nums[R]]) #这里面的去重非常巧妙，这两个while的设置
while L < R and nums[L] == nums[L+1]: #去重第二个元素
L +=1
while L < R and nums[R] == nums[R-1]:#去重第三个元素
R -=1
L +=1
R -=1
elif nums[i] + nums[L] + nums[R] < 0 :
L +=1
else:
R -=1
return res
第18题. 四数之和
题目链接：
18. 四数之和 - 力扣（Leetcode）
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]: continue # 对nums[i]去重
for k in range(i+1, n):
if k > i + 1 and nums[k] == nums[k-1]: continue # 对nums[k]去重
p = k + 1
q = n - 1
while p < q:
if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
else:
res.append([nums[i], nums[k], nums[p], nums[q]])
# 对nums[p]和nums[q]去重
while p < q and nums[p] == nums[p + 1]: p += 1
while p < q and nums[q] == nums[q - 1]: q -= 1
p += 1
q -= 1
return res
两层循环+双指针
