出现概率：约10%。这是一道动态规划+排列组合的综合应用题。同学，你这里用递归的话你的这个时间复杂度得有多少？我们这个数组一旦有几十个元素的话，你这还能跑得动吗？
参考代码：
import numpy as np
def permutations(arr):
if len(arr)<=1:
return([arr])
t = [arr[0:1]]
i = 1
while i<=len(arr)-1:
a = arr[i]
t = [xs[0:j]+[a]+xs[j:] for xs in t for j in range(i+1)]
t = np.unique(t,axis=0).tolist()
i = i+1
return(t)
print(permutations([1,1,3]))
输出结果：
[[1, 1, 3], [1, 3, 1], [3, 1, 1]]
10，三数之和
题目形式：给定一个���组和目标数target，找出数组中a,b,c满足 a+b+c = target 的所有组合。例如：arr = [-3,-1,-2,1,2,3]，target = 0。输出为 [(-3,1,2),(-2,-1,3)]
题目难度：困难
出现概率：约5%。这是一道非常有技巧的题目。你可以尝试先将arr排序。注意，我们的时间复杂度要求为O(n**2) ，空间复杂度要求O(1)，对，就是这么严格，你要好好想想……哟，有思路啦……emmm……大体上符合要求……同学，你现在手上还有其他家的offer吗？
参考代码：
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res =[]
i = 0
for i in range(len(nums)):
if i == 0 or nums[i]>nums[i-1]: ## 这个一步很重要
l = i+1
r = len(nums)-1
while l < r:
s = nums[i] + nums[l] +nums[r]
if s ==0:
res.append([nums[i],nums[l],nums[r]])
l +=1
r -=1
while l < r and nums[l] == nums[l-1]: ## 优化
l += 1
while r > l and nums[r] == nums[r+1]: ## 优化
r -= 1
elif s>0:
r -=1
else :
l +=1
return res
输出结果：
[(-2, -1, 3), (-3, 1, 2)]
Linux公社的RSS地址：https://www.linuxidc.com/rssFeed.aspx