九键输入组合与四数之和——LeetCode 16、17 题记
九键输入组合与四数之和——LeetCode 16、17 题记
同样是两道中等难度题目，但题目间没啥关联：第一道类似于我们之前按键手机时代九键输入组合的展示，第二道题将昨天的三数之和改造成了四数之和。现在做题，有时候做着做着提交通过了，就不愿深挖了，挺偷懒的，希望写题记时可以多拓展学习下。
题目一
第 17 题 电话号码的字母组合：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例：
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].好吧，数字 1 键还没内容，叫它八键组合得了。
思路
首先是数字转字母的过程：我们输入 "23" 那么要先取到 "2" 对应的 "abc" 和 "3" 对应的 "def"。然后我们将二者拆分组合得到结果。
数字转字母这个过程，吸取之前题目中的经验，事先写好一个不同数字对应不同字母的字典，一来哈希字典方便快速查找，二来也省的代码提取麻烦。
将字母串拆分组合这步，没想到特别好的方法，我是先把 "abc" 转化成单字母列表，遍历 "def" 每一步都在之前的列表所有元素尾加上新遍历的字母，不断扩充列表拿到结果，细节我们看代码。
代码
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 如果输入空字符串，返回空列表
if digits=="":
return []
# 用字典存好数字与字母的对应关系
table = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
# digits[0] 即输入字符串的第一位数字，table[该数字]取到对应字母串，转成列表
lst = list(table[digits[0]])
# 获取输入数字串长度用于遍历
l = len(digits)
i=1
# while 循环对每一位数字进行一次处理
while i<l:
# temp_sum 列表用于循环中保存生成的结果
temp_sum=[]
# 对第 i 位数字串对应的字母串中每个字母进行遍历
for c in table[digits[i]]:
# 对于之前字母的列表、每一个元素后添加新字母，生成新的列表
temp = [x+c for x in lst]
# for 循环中每个列表结果都添加到 temp_sum 结果中
temp_sum += temp
# for 循环结束，将生成的结果赋值给 lst 用于后续扩展
lst = temp_sum
# i 自增用于遍历下一位
i+=1
# while 循环结束，返回 lst 结果即可
return(lst)提交答案
结果有些出乎意料，因感觉可能存在些更好的方法来生成这些字母组合列表：
执行用时 : 40 ms, 在所有 Python3 提交中击败了 53.39% 的用户 内存消耗 : 13.6 MB, 在所有 Python3 提交中击败了 5.41%的用户
优化
其实代码中的 while 循环换成 for 也行，不知当时怎么就选择了 while。至于改进生成字母组合就没啥想法了，直接去题解与评论里观摩，发现两种可以借鉴的思路：回溯法和 pythonic 的列表推导式应用。
回溯法我们之前在第十题正则表达式那道题目中遇到过，这里贴代码参考下：
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits: return []
# 这比我还细心，直接弄成列表了
phone = {'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']}
# backtrack 即回溯中不断调用的函数，
def backtrack(combination,nextdigit):
# 如果下一位为空
if len(nextdigit) == 0:
# 结果中添加 combination
res.append(combination)
else:
# 对数字对应的每个字母，都会再调用 backtrack 来进行回溯
for letter in phone[nextdigit[0]]:
backtrack(combination + letter,nextdigit[1:])
res = []
backtrack('',digits)
return res
#作者：z1m
#链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/hui-su-dui-lie-tu-jie-by-ml-zimingmeng/说实话，即使是看着写好的代码，也要再举个具体实例配合着看才能弄明白，还是有些难度的。
还有个就是很 Pythonic 的列表推导式应用：
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
conversion={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
if len(digits)==0:
return []
product=['']
# 双层for循环的列表推导式
for k in digits:
product=[i+j for i in product for j in conversion[k]]
return product
#作者：jutraman
#链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/pythondian-hua-hao-ma-de-zi-mu-zu-he-by-jutraman/双层 for 循环的列表推导式，我佛了，同样属于看得懂但仍不会用系列，且学且膜拜中。
今天也是刷两道题，继续走起～
题目二
第 18 题 四数之和：
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/4sum思路
昨天刚做完两道和三数求和相关的题目，当时的思路是遍历第一个数，对剩下的两个数通过双指针法进行定位。今天这题目虽然是四数之和，但倘若我们把第一个数抽出来、那也就还原成了三数之和的问题，所以解决方法就是对第一个数进行遍历，在其后范围内遍历第二个数，剩下的第三和第四个数用双指针法来定位。
当然，过程也是类似，为了方便检索过程，对列表排个序。但防止结果中出现重复列表这步，感觉没法套用之前那种遇到相同元素就跳过，我直接用了 if 新结果 not in 结果列表 的判断来实现的，没想到还能通过测试。
代码
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
# result 用于存结果
result = []
# 对列表排序
nums.sort()
l = len(nums)
# 不够 4 个数的列表返回空列表
if l<4:
return result
# 第一个数用 i 表示
for i in range(l-2):
# 第二个数用 j 表示，它在 i 之后
for j in range(i+1,l-1):
# 根据目标和，计算剩余两个数的和
temp = target - nums[i] - nums[j]
# x 和 y 双指针代表第三和第四个数
x,y = j+1,l-1
# while 循环双指针缩小范围以获取能达到目标和的组合
while x<y:
sum_xy = nums[x]+nums[y]
# 如果第三四个数的和小于要求的和，右移 x
if sum_xy<temp:
x += 1
# 如果第三四个数的和大于要求的和，左移 y
elif sum_xy>temp:
y -= 1
# 如果恰好等于，说明 i,j,x,y 对应四个数是要找的组合
else:
# 用个列表推导式来简化写法，生成四个数组成的列表
one = [nums[p] for p in (i,j,x,y)]
# 用此判断结果中是否有重复
if one not in result:
result.append([nums[p] for p in (i,j,x,y)])
# 同时移动 x 和 y 继续查找
x += 1
y -= 1
return result提交答案
最终防止出现重复结果这步最初是偷懒用了 if not in 来进行判断，没想到结果表现还可以：
执行用时 : 876 ms, 在所有 Python3 提交中击败了 53.17% 的用户 内存消耗 : 13.6 MB, 在所有 Python3 提交中击败了 6.52% 的用户
优化
优化点在于查是否重复的步骤，类似于之前三数之和时对下一位判断是否与当前位相同，相同则跳过，今天有些来不及细化完成了。翻看了下题解区其它解法，多数也是基于双指针法，也有大致思路和我一致的，这就挺开心了。
结论
第 17 和 18 题，两道均为中等难度题，第一个是循环遍历的思路，第二个是基于之前三数之和的变形、仍然用到双指针法。
但第一题参考题解中的回溯法和看起来很拉风的嵌套 for 循环列表推导式的方法，目前也只是看得懂但用不来阶段，很受启发。
可能挖得还是不深，时间有点紧张，先这样吧。。。