题目
引用自:LeetCode-中等-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
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0 输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [1,0,-1,0,-2,2], target = 0 输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
提示:
- 1 <= nums.length <= 200
- -109 <= nums[i] <= 109
- -109 <= target <= 109
解题:
没什么好说的(老一句),
方法一:
暴力破解,4层循环,挨个判断,注意从前到后的顺序,4个元素别抽取重复就好。抽取出来的4个元素如果满足target条件,则检查是不是跟以前的答案有重复,有的话就丢掉,没重复的话就添加到数组(列表)存起来,(其中判断重复的那一部分,可以先把这4个数排序,方便检查,然后跟以前存储下来的答案检查,无重复的话直接把这个排好序的4个元素数组(列表)存起来,这样每次判断的时候,从存起来的答案里面抽出来的4位数组,就不需要重新排序了,因为放进去的时候就是排好序的。同时,每次判断重复时,可以判断前3个数就行,因为前三个数字如果都相同,那么第四个数肯定也一样,因为num1 + num2 + num3 + num4 == target,target和三个数确定之后,第四个数自然也确定了)。O(n^4)
方法二
双指针,先将整个数组排序,然后跟方法一 一样,挨个检查,只是不用4层循环,用两层循环,加一个双指针。外边两层也是和方法一的外两层一样,但是每次迭代里面,用一个双指针,一个从左往右(这里并不是从整个数组的最左开始,看代码),一个从右往左(这个右就从数组末尾开始了),每次判断外层循环的两个数和指针滑动的两个数,这四个数之和是等于target,还是大于或者小于target,如果小于target,说明我们应该适当把这4个数里的某些数调大,由于数组又是已经排序过的,所以就把左指针往右滑动一下,这样,左指针指向的数有可能就会变大,再进行和判断,同理,如果大于target,那就把右指针向左移。如果刚好等于target,那就去判断有没有跟以前存下来的答案重复(因为整个数组提前排好序了,所以直接检查,不需要重新把这4个数排序),检查完,继续把左指针向右移动一下(或者右指针向左移动一下,这两个都可以),直到左右指针相遇。
O(nlogn + n^3),排序是O(nlogn),迭代是两层加双指针,相当于3层迭代。
方法一:
#方法一:leetcode提交的时候超时了,因为时间复杂度高 # 四层循环解法 class Solution: def fourSum(self, nums, target): self.result = [] length = len(nums) if length < 4: return [] i = 0 while i < length - 3: j = i + 1 while j < length - 2: k = j + 1 while k < length - 1: l = k + 1 while l < length: if nums[i] + nums[j] + nums[k] + nums[l] == target: self.deal_same([nums[i], nums[j], nums[k], nums[l]]) l += 1 k += 1 j += 1 i += 1 return self.result def deal_same(self, list_four): if len(self.result) < 1: list_four = sorted(list_four) self.result.append(list_four) list_four = sorted(list_four) for res in self.result: if list_four[0] == res[0] and list_four[1] == res[1] and list_four[2] == res[2]: return self.result.append(list_four)
#方法二:leetcode提交通过, (记得Solution1换成Solution) #双指针解法 class Solution1: def fourSum(self, nums, target): nums = sorted(nums) self.result = [] length = len(nums) if length < 4: return [] i = 0 while i < length - 3: j = i + 1 while j < length - 2: k = j + 1 l = length - 1 while l > k: sum = nums[i] + nums[j] + nums[k] + nums[l] if sum > target: l -= 1 elif sum < target: k += 1 else: self.deal_same([nums[i], nums[j], nums[k], nums[l]]) k += 1 j += 1 i += 1 return self.result def deal_same(self, list_four): if len(self.result) < 1: self.result.append(list_four) for res in self.result: if list_four[0] == res[0] and list_four[1] == res[1] and list_four[2] == res[2]: return self.result.append(list_four)测试:
# 四层循环解法 class Solution: def fourSum(self, nums, target): self.result = [] length = len(nums) if length < 4: return [] i = 0 while i < length - 3: j = i + 1 while j < length - 2: k = j + 1 while k < length - 1: l = k + 1 while l < length: if nums[i] + nums[j] + nums[k] + nums[l] == target: self.deal_same([nums[i], nums[j], nums[k], nums[l]]) l += 1 k += 1 j += 1 i += 1 return self.result def deal_same(self, list_four): if len(self.result) < 1: list_four = sorted(list_four) self.result.append(list_four) list_four = sorted(list_four) for res in self.result: if list_four[0] == res[0] and list_four[1] == res[1] and list_four[2] == res[2]: return self.result.append(list_four) #双指针解法 class Solution1: def fourSum(self, nums, target): nums = sorted(nums) self.result = [] length = len(nums) if length < 4: return [] i = 0 while i < length - 3: j = i + 1 while j < length - 2: k = j + 1 l = length - 1 while l > k: sum = nums[i] + nums[j] + nums[k] + nums[l] if sum > target: l -= 1 elif sum < target: k += 1 else: self.deal_same([nums[i], nums[j], nums[k], nums[l]]) k += 1 j += 1 i += 1 return self.result def deal_same(self, list_four): if len(self.result) < 1: self.result.append(list_four) for res in self.result: if list_four[0] == res[0] and list_four[1] == res[1] and list_four[2] == res[2]: return self.result.append(list_four) if __name__=="__main__": so = Solution() so1 = Solution1() print('测试1: nums=[3,2,2,3,2], target=9') print('4层循环t',so.fourSum(nums=[3,2,2,3,2], target=9)) print('双指针t',so1.fourSum(nums=[3,2,2,3,2], target=9)) print() print('测试2: nums=[1,0,-1,0,-2,2], target=0') print('4层循环t', so.fourSum(nums=[1,0,-1,0,-2,2], target=0)) print('双指针t', so1.fourSum(nums=[1,0,-1,0,-2,2], target=0))
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)