【leetcode系列】【py3】【中等】四数之和
题目:
原题链接: https://leetcode-cn.com/problems/4sum/
解题思路:
与三数之和思路相同,只是外面再套一层循环
详见: https://blog.****.net/songyuwen0808/article/details/105073878
代码实现:
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
num_len = len(nums)
if num_len < 4:
return []
res_lst = []
nums.sort()
for index1 in range(0, num_len - 3):
if index1 > 0 and nums[index1] == nums[index1 - 1]:
continue
for index2 in range(index1 + 1, num_len - 2):
if index2 > index1 + 1 and nums[index2] == nums[index2 - 1]:
continue
sum_12 = nums[index1] + nums[index2]
left, right = index2 + 1, num_len - 1
while left < right:
sum_all = sum_12 + nums[left] + nums[right]
if sum_all == target:
res_lst.append([nums[index1], nums[index2], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif sum_all > target:
right -= 1
else:
left += 1
return res_lst