有趣网站建设无聊,嘉兴五县两区网站建设,手机网站开发设计包括什么,泰安网站营销推广给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意#xff1a;答案中不可以包含重复的三元组。 示例 1判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 示例 1 输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 解释 nums[0] nums[1] nums[2] (-1) 0 1 0 。 nums[1] nums[2] nums[4] 0 1 (-1) 0 。 nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意输出的顺序和三元组的顺序并不重要。 示例 2 输入nums [0,1,1] 输出[] 解释唯一可能的三元组和不为 0 。 示例 3 输入nums [0,0,0] 输出[[0,0,0]] 解释唯一可能的三元组和为 0 。 提示 3 nums.length 3000 - 1 0 5 10^5 105 nums[i] 1 0 5 10^5 105 这个问题其实不难对于我来说还是那个经验在你的想象力不够好的情况下拿一个例子来求解很多细节问题就清楚了。
我想到了先进行排序然后抽取一个数再遍历数组找出另外两个数使三个数和为零但是细节想失误了认为从一个数组中找出所有和为指定值的组合需要 O ( n 2 ) O(n^2) O(n2), 实际需要 O ( n ) O(n) O(n), 关键还是没动手。
class Solution:def threeSum(self, nums: list) - list:#升序排序nums sorted(nums, keylambda x:x, reverseFalse)if nums[0] 0 or nums[len(nums) - 1] 0:return []if min(nums) 0 and max(nums) 0:return [[0,0,0]]result []for i in range(len(nums)):#不重复if (i 0) and nums[i-1] nums[i] or nums[i] 0:continuenum nums[i]t self.twoSum(nums[i 1:], num)if t:result.extend(t)return resultdef twoSum(self, nums, value):target -valuer []p, q 0, len(nums) - 1while p q:t nums[p] nums[q]if t target:r.append([value, nums[p], nums[q]])while p q:if nums[p1] ! nums[p]:p 1breakelse:p 1while p q:if nums[q-1] ! nums[q]:q - 1breakelse:q - 1elif t target:p 1else:q - 1if len(r) 0:return Noneelse:return r
代码的第12,13行主要针对排序后的数组有连续的相同数字可以思考下为什么这么写。
