代码随想录一一一哈希表一一一四数之和

题目来源自leetcode与代码随想录

（1）18.四数之和

题目描述：
给你一个由 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

解题思路：
和15.三数之和linkkkkkkkk相同，只是多加了一层嵌套 时间复杂度从02->03

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:nums.sort()L = len(nums)res = []for i in range(L):if i > 0 and nums[i]==nums[i-1]:continuefor k in range(i+1, L):if k > i+1 and nums[k]==nums[k-1]:continueleft, right = k+1, L-1while left < right:if nums[i] + nums[k] + nums[left] + nums[right] > target: right -= 1elif nums[i] + nums[k] + nums[left] + nums[right] < target: left += 1else:res.append([nums[i], nums[k], nums[left], nums[right]])while left < right and nums[left] == nums[left + 1]: left += 1while left < right and nums[right] == nums[right - 1]: right -= 1left += 1right -= 1return res

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！