Day7:Hash2
- Leetcode 454: 4sum2
- Leetcode 383: Ransom Note
- Leetcode 15: 3 sum
- Leetcode 18: 4 sum
Leetcode 454: 4sum2
from collections import Counter
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
hashtable = Counter()
for num1 in nums1:
for num2 in nums2:
hashtable[num1+num2]+=1
count = 0
for num3 in nums3:
for num4 in nums4:
key = - num3 - num4
if key in hashtable:
count+=hashtable[key]
return count
Leetcode 383: Ransom Note
from collections import Counter
class Solution:
def canConstruct(self, r: str, m: str) -> bool:
count1 = Counter()
count2 = Counter()
for s1 in r:
count1[s1]+=1
for s2 in m:
count2[s2]+=1
for s1 in r:
if count2[s1]==0:
return False
if count2[s1]<count1[s1]:
return False
return True
Leetcode 15: 3 sum
暴力 时间没过
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
for i in range(len(nums)-2):
for j in range(i+1, len(nums)-1):
for k in range(j+1, len(nums)):
pos = [nums[i],nums[j],nums[k]]
pos = sorted(pos)
if sum(pos) == 0 and pos not in res:
res.append(pos)
return res
双指针 恶心 过不了 time 思路正确
if len(nums)<3: return []
nums, res = sorted(nums), []
for i in range(len(nums)-2):
left, right = i + 1, len(nums) - 1
# remove duplicate of first element
if res != [] and res[-1][0] == nums[i]: continue
while left<right:
if nums[i]+nums[left]+nums[right] == 0:
res.append([nums[i],nums[left],nums[right]])
# remove duplicate of 2nd element
while left < right-1 and nums[left] == nums[left + 1]:
left+=1
# remove duplicate of 3rd element
while right>left+1 and nums[right] == nums[right - 1]:
right-=1
if nums[i]+nums[left]+nums[right]>0:
right-=1
else:
left += 1
return res
Leetcode 18: 4 sum
一样的思路 多加一个loop
chatgpt写的 哈哈哈哈哈哈哈
n = len(nums)
nums.sort()
res = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n - 2):
if j > i+1 and nums[j] == nums[j-1]:
continue
left = j + 1
right = n - 1
while left < right:
s = nums[i] + nums[j] + nums[left] + nums[right]
if s == target:
res.append([nums[i], nums[j], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
elif s < target:
left += 1
else:
right -= 1
return res
更多推荐
Day7:Hash2
发布评论