'''
给定输入数组，输出4元对列表，列表中每个元素是一个列表，子列表数值之和为target
'''
class Solution:
def fourSum(self, nums, target: int):
def select_sort(nums):
# 对输入数据进行选择排序
# 选择排序算法是对冒泡排序算法的改进
# 冒泡排序算法是在每次循环中，找到未排序数组中的最大值，以小步慢跑式的比较和交换将其移动到数组的末尾
# 而选择排序则是在每次循环中，找到当前未排序子序列中的最大值，记录其下标，再将它与末尾元素进行交换
# 直接将最大的元素一次性移动到它合适的位置，
# 选择排序算法和插入排序算法的区别之处在于：
# 选择排序算法中，无序的前缀子序列中的数值都要小于有序的后缀子序列的第一个元素（即有序子序列的最小值）
# 插入排序算法中，无序的后缀子序列中的数值可能大于有序前缀子序列中的数值，也可能小于
if len(nums)<=1:
return nums
unsorted_length=len(nums)
for i in range(len(nums)-1,-1,-1):
# 从无序的前缀子序列中找到最大值,以及最大值在数组中的索引下标，将其与nums[i]数值交换
max_value=-float("inf")
max_index=-1
for j in range(unsorted_length):
if nums[j]>max_value:
max_value=nums[j]
max_index=j
unsorted_length-=1
nums[max_index]=nums[i]
nums[i]=max_value
return nums
output = []
if len(nums)<=3:
return output
sorted_array=select_sort(nums)
# print(sorted_array)
if (sorted_array[0]>target and target>0):
return output
if len(nums)==4:
if nums[0]+nums[1]+nums[2]+nums[3]==target:
output.append(nums)
return output
else:
return output
for i in range(len(sorted_array)-3):
if i>=1 and sorted_array[i]==sorted_array[i-1]:
continue
if (sorted_array[i]>target and target>0) or sorted_array[i]+sorted_array[i+1]+sorted_array[i+2]+sorted_array[i+3]>target:
# print('here',i)
return output
if i==len(sorted_array)-4:
if sorted_array[-1]+sorted_array[-2]+sorted_array[-3]+sorted_array[-4]==target:
output.append([sorted_array[-4],sorted_array[-3],sorted_array[-2],sorted_array[-1]])
return output
for j in range(i+1,len(sorted_array)-2):# 找到3个数的和为目标值
if sorted_array[i]+sorted_array[j]>target and target>0:
break
if j>i+1 and sorted_array[j]==sorted_array[j-1]:
# print(j,sorted_array[j])
continue
start=j+1
end=len(sorted_array)-1
while(start<end):
sum=sorted_array[i]+sorted_array[j]+sorted_array[start]+sorted_array[end]
if sum==target:
output.append([sorted_array[i],sorted_array[j],sorted_array[start],sorted_array[end]])
while (start < end and sorted_array[start] == sorted_array[start + 1]):
start += 1
while (start < end and sorted_array[end] == sorted_array[end - 1]):
end -= 1
start+=1
end-=1
elif sum<target:
while(start<end and sorted_array[start]==sorted_array[start+1]):
start+=1
start+=1
else:
while(start<end and sorted_array[end]==sorted_array[end-1]):
end-=1
end-=1
# print('output=')
return output
if __name__=="__main__":
nums =[-1,0,-5,-2,-2,-4,0,1,-2]
print(Solution().fourSum(nums,-9))
