哈哈,继续在前两天的基础之上,4 Sum问题
https://leetcode-cn.com/problems/4sum/description/
对于这种列表的题目,继续要排个序,开始想过类似分治的方法,但好像路走不通,那么本着解决问题的思路,就先继续“退化”的路,这里就是通过循环,把4Sum变成了3Sum,然后再变成2Sum,基于排序,那么就可以用双指针法。
原本写出来之后,以为会超时,但没想到竟然低分飘过了。
现在回过来看,应该还是有不少可以优化的地方,这个计划就留到周末去吧,平时工作日就先争取刷一道题,就理解一种思路,顺便继续熟悉了Python的代码range的用法,对于一个写惯了Java的人来说,这种基于range的循环还是需要适应下。
尽管贡献了一个效率比较低的代码,但实际就可读性和理解方面还是比较清晰的【好吧,其实就是算法比较挫啦】
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
ret = set()
for i in range(len(nums)-3):
for j in range(i+1,len(nums)-2):
t = -(nums[i] + nums[j])+target
l = j+1
r = len(nums)-1
while l<r:
two_sum = nums[l] + nums[r]
if two_sum == t:
ret.add((nums[i],nums[j],nums[l],nums[r]))
l+=1
r-=1
elif two_sum < t:
l+=1
elif two_sum > t:
r-=1
return list(ret)