一、15. 三数之和
提示
中等
6.5K
相关企业
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
class Solution:
def threeSum(self,nums):
n=len(nums)
res=[]
if n<3:
return []
nums.sort()
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 L<R and nums[L]==nums[L+1]:
L=L+1
while L<R and nums[R]==nums[R-1]:
R=R-1
L=L+1
R=R-1
elif nums[i]+nums[L]+nums[R]>0:
R=R-1
else:
L=L+1
return res
nums = [-1,0,1,2,-1,-4]
res=Solution()
rrr=res.threeSum(nums)
print(rrr)
二、205. 同构字符串
简单
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例 1:
输入：s = “egg”, t = “add”
输出：true
示例 2：
输入：s = “foo”, t = “bar”
输出：false
示例 3：
输入：s = “paper”, t = “title”
输出：true
from collections import Counter, defaultdict
def isIsomorphic(s, t):
if not s:
return True
dic = {}
for i in range(len(s)):
if s[i] not in dic:
if t[i] in dic.values():
return False
else:
dic[s[i]] = t[i]
else:
if dic[s[i]] != t[i]:
return False
return True
三、383. 赎金信
简单
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false
示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false
示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true
解题思路
1、遍历set集合，避免重复遍历
2、如果 magazine 字符串中字符 i 出现的次数小于出现在 ransomNote 中的次数则返回 False
3、集合遍历完成则返回 True
def canConstruct(ransomNote, magazine):
ransomNote_set = set(ransomNote)
for i in ransomNote_set:
if magazine.count(i) < ransomNote.count(i):
return False
return True
ransomNote = "a"
magazine = "b"
print(canConstruct(ransomNote, magazine))
