一、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))