16. 3Sum Closest
跟3sum差不多 沒啥
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
ans = None
cur_dis = 10**5
for i in range(n-2):
l,r = i+1, n-1
while l<r:
diff = nums[i]+nums[l]+nums[r]-target
if abs(diff)<cur_dis:
ans = nums[i]+nums[l]+nums[r]
cur_dis = abs(diff)
if diff>0:
r -= 1
elif diff<0:
l += 1
else:
return target
return ans
17. Letter Combinations of a Phone Number
就backtracking硬幹 好像也沒啥
只是手打那個map好麻煩 直接給chatgpt打
def letterCombinations(self, digits: str) -> List[str]:
mp = {
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z']
}
ans = []
n = len(digits)
def dfs(cur_list, idx):
if idx==n:
if cur_list:
ans.append("".join(cur_list))
return
for cur_c in mp[digits[idx]]:
dfs(cur_list+[cur_c], idx+1)
dfs([], 0)
return ans
525. Contiguous Array
幹還真的忘記了
好tricky 希望我會記住它
恨525
def findMaxLength(self, nums: List[int]) -> int:
mp = {0: -1}
prefix = 0
ans = 0
for idx, num in enumerate(nums):
prefix += 1 if num==1 else -1
if prefix not in mp:
mp[prefix] = idx
else:
ans = max(ans, idx-mp[prefix])
return ans