搬瓦工的主机可以用来做网站吗,东营网站优化,成品网站货源1688免费推荐,国家开发银行网站解题思路
最开始是打算沿着二数之和的思路做#xff0c;即固定了最大的#xff0c;然后小的开始遍历#xff0c;因为这种遍历方式只需要遍历一轮就能完成#xff0c;所以复杂度应该是O#xff08;n2#xff09;#xff0c;但是最后几个示例还是超时了#xff0c;可能进…解题思路
最开始是打算沿着二数之和的思路做即固定了最大的然后小的开始遍历因为这种遍历方式只需要遍历一轮就能完成所以复杂度应该是On2但是最后几个示例还是超时了可能进一步优化还是可以做的。但是事实上我最开始就在寻找一个能够约束剩余两个变量的方法因为不重复我们可以添加大小关系的假设但是脑子里一直是两个指针在一个遍历中移动所以没搞出来。事实上是一个变量变大另一个变量的上限减小可以基于这个想法做。
未AC代码最后样例超时
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:def get_res(index, k):disk {}res []for i, n in enumerate(nums[:index]):if n - k // 2:if n -k // 2 and n in disk and n n k 0:res.append([n, n, k]) disk[-k - n] ielse:if n in disk:res.append([n, - n - k, k])return resres []nums.sort()for i in range(-1, -len(nums) - 1, -1):temp get_res(i, nums[i])for t in temp:if t not in res:res.append(t)return res官方题解
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:n len(nums)nums.sort()ans list()# 枚举 afor first in range(n):# 需要和上一次枚举的数不相同if first 0 and nums[first] nums[first - 1]:continue# c 对应的指针初始指向数组的最右端third n - 1target -nums[first]# 枚举 bfor second in range(first 1, n):# 需要和上一次枚举的数不相同if second first 1 and nums[second] nums[second - 1]:continue# 需要保证 b 的指针在 c 的指针的左侧while second third and nums[second] nums[third] target:third - 1# 如果指针重合随着 b 后续的增加# 就不会有满足 abc0 并且 bc 的 c 了可以退出循环if second third:breakif nums[second] nums[third] target:ans.append([nums[first], nums[second], nums[third]])return ans
