leetcode--四数之和(解题思路+详细代码注释)Python实现版

1.题目

给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1

输入nums = [1,0,-1,0,-2,2], target = 0
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2

来源力扣LeetCode
链接https://leetcode.cn/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。

解题思路

           排序+双指针法

代码如下

class Solution:
    def sishuzhihe1(self,shuzu:list[int],target:int):
#最终返回数组
        zuihoujieduo =[]
# 对数组排序
        shuzu.sort()
# 记录数组的长度
        changdu = len(shuzu)
#两次遍历
        for i in range(changdu):
#去重i
            if i >= 1 and [i - 1] == shuzu[i]:
                continue
            for j in range(i+1,changdu):  #起始是i+1
#去重j
                if j > i +1 and shuzu[j-1] == shuzu[j]:
                    continue #跳过循环
# i和j去重完后
# 定义左右指针
                left = j +1  #右边的值
                right = changdu - 1 # 最右边的数是最大的
                while left < right:
# 在i和j固定的情况下不停的找左右指针
# 求四数之和因为这会已经有四个指针了
                  qiuhe = shuzu[i] +shuzu[j] +shuzu[left] +shuzu[right]
#判断 如果四数之和大于目标值
                  if qiuhe > target:
# 右边值要向左边走
                    right -= 1
# 如果目标值小于四数之和
                  elif qiuhe < target:
                    left += 1
                  else:
#记录一下输出结果的值
                    zuihoujieduo.append([shuzu[i],shuzu[j],shuzu[left],shuzu[right]])
#这时要对左右指针进行去重
                    while left < right and shuzu[left + 1] == shuzu[left]:
                        left += 1
                    while left < right and shuzu[right - 1] == shuzu[right]:
                        right -= 1
# 更新左右指针
                    left += 1
                    right -= 1
# 最终返回数组
        return  zuihoujieduo
sishuzhihe=Solution()
er=sishuzhihe.sishuzhihe1(shuzu=[1,0,-1,0,-2,2],target=0)
print(er)

结果如下

[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]