Leetcode HOT100 经典题目三数之和题目给定一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。3 nums.length 3000-10^5 nums[i] 10^5人话翻译一遍就是给定一个整数数组数组长度在3~3000之间并且数组中每个数的值在-10^5到10^5之间。需要在个数组中找出可能的多个三元组使三元组中的数字之和为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 。错误案例[ [0,1,-1] , [-1,0,1] ]因为 [0,1,-1] 和 [-1,0,1] 两个三元组的组成数字是相同的。解题思路这道题较为常规的解法是使用双指针。先对原数组进行一次排序此处选择从小到大升序排序排完序后使得指针在数组上的移动变得有方向性。在数组外套一层循环设置变量 i (range(len(nums-2)))再设两个指针left和right分别指向 i1和 len(nums)-1。两个指针在区间 i1~len(nums)-1 上移动寻找三数相加为0的数字组合。首先对特殊情况进行判断当nums数组长度等于三时只需要判断三数相加之和是否为0即可。lengthlen(nums) if length3: if sum(nums)0: return [nums] else: return []若nums数组长度大于3则首先对数组进行排序并声明返回数组。对排序后的数组进行判断存在两种特殊情况1.排序后数组最后一位元素小于02.排序后数组首位元素大于0。这两种情况都不可能存在相加等于0的三元组可以直接返回空数组。new_numssorted(nums) if new_nums[0]0 or new_nums[-1]0: return [] result[]对数组设置一个外层循环范围 0 ~ len(nums)-3 此处末值取 len(nums)-3 是因为最后一种情况为最后三个数组成三元组此时 i 不需要走到最后一位走到倒数第三位后面还有 left 和 right 两个指针的位置。令 sums 为 ileft 和 right 三个数的和。此时出现三种情况1. sum0 说明此时整体和偏小需要更大的值故 new_nums(left) 需要增大left12. sum0 说明此时整体和偏大需要小一些的值故 new_nums(right) 需要减小right-13. sum0 此时三数之和正好等于0将该三元组添加至 result 。 此时小于 left 已经确定没有能组成三元组的值故 left1 。由于数组是升序排列left 数值变大需要更小的数值来平衡等式故 right 数值减小right-1。这时出现一个判断若 new_nums[left]new_nums[left-1] 即增加后的 left 对应值与增加前的值相等这会导致出现重复的三元组需要跳过相同的值。使用 while 循环进行跳值直到 left 对应值变为不同的值。同理当 left 和 right 指针移动到头无法再移动时递增 i 的值。若 i 递增后序号对应值与递增前相等也会导致三元组重复。故使用 continue 跳过此次循环。for i in range(length-2): if i1: if new_nums[i]new_nums[i-1]: continue if new_nums[i]0 and new_nums[i1]0: break lefti1 rightlength-1 while leftright: sumsnew_nums[i]new_nums[left]new_nums[right] if sums0: result.append([new_nums[i],new_nums[left],new_nums[right]]) left1 while leftright and new_nums[left-1]new_nums[left]: left1 right-1 elif sums0: right-1 else: left1由此循环即可得出最终三元组数组并返回。完整代码如下class Solution(object): def threeSum(self, nums): :type nums: List[int] :rtype: List[List[int]] lengthlen(nums) # 长度等于3特殊情况 if length3: if sum(nums)0: return [nums] else: return [] # 对原数组进行排序得到升序排序的新数组 new_numssorted(nums) # 判断全为正数或全为负数的特殊情况 if new_nums[0]0 or new_nums[-1]0: return [] result[] # 对数组进行循环 for i in range(length-2): # 若i对应值与递增之前相同直接跳过 if i1: if new_nums[i]new_nums[i-1]: continue # 若后面全是正数直接结束循环 if new_nums[i]0 and new_nums[i1]0: break lefti1 rightlength-1 # 使用while循环移动左右指针 while leftright: sumsnew_nums[i]new_nums[left]new_nums[right] if sums0: result.append([new_nums[i],new_nums[left],new_nums[right]]) left1 # 判断后面数是否与前数重复 while leftright and new_nums[left-1]new_nums[left]: left1 right-1 elif sums0: right-1 else: left1 return result
【PY】Leetcode-15 三数之和 python代码+解析
Leetcode HOT100 经典题目三数之和题目给定一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。3 nums.length 3000-10^5 nums[i] 10^5人话翻译一遍就是给定一个整数数组数组长度在3~3000之间并且数组中每个数的值在-10^5到10^5之间。需要在个数组中找出可能的多个三元组使三元组中的数字之和为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 。错误案例[ [0,1,-1] , [-1,0,1] ]因为 [0,1,-1] 和 [-1,0,1] 两个三元组的组成数字是相同的。解题思路这道题较为常规的解法是使用双指针。先对原数组进行一次排序此处选择从小到大升序排序排完序后使得指针在数组上的移动变得有方向性。在数组外套一层循环设置变量 i (range(len(nums-2)))再设两个指针left和right分别指向 i1和 len(nums)-1。两个指针在区间 i1~len(nums)-1 上移动寻找三数相加为0的数字组合。首先对特殊情况进行判断当nums数组长度等于三时只需要判断三数相加之和是否为0即可。lengthlen(nums) if length3: if sum(nums)0: return [nums] else: return []若nums数组长度大于3则首先对数组进行排序并声明返回数组。对排序后的数组进行判断存在两种特殊情况1.排序后数组最后一位元素小于02.排序后数组首位元素大于0。这两种情况都不可能存在相加等于0的三元组可以直接返回空数组。new_numssorted(nums) if new_nums[0]0 or new_nums[-1]0: return [] result[]对数组设置一个外层循环范围 0 ~ len(nums)-3 此处末值取 len(nums)-3 是因为最后一种情况为最后三个数组成三元组此时 i 不需要走到最后一位走到倒数第三位后面还有 left 和 right 两个指针的位置。令 sums 为 ileft 和 right 三个数的和。此时出现三种情况1. sum0 说明此时整体和偏小需要更大的值故 new_nums(left) 需要增大left12. sum0 说明此时整体和偏大需要小一些的值故 new_nums(right) 需要减小right-13. sum0 此时三数之和正好等于0将该三元组添加至 result 。 此时小于 left 已经确定没有能组成三元组的值故 left1 。由于数组是升序排列left 数值变大需要更小的数值来平衡等式故 right 数值减小right-1。这时出现一个判断若 new_nums[left]new_nums[left-1] 即增加后的 left 对应值与增加前的值相等这会导致出现重复的三元组需要跳过相同的值。使用 while 循环进行跳值直到 left 对应值变为不同的值。同理当 left 和 right 指针移动到头无法再移动时递增 i 的值。若 i 递增后序号对应值与递增前相等也会导致三元组重复。故使用 continue 跳过此次循环。for i in range(length-2): if i1: if new_nums[i]new_nums[i-1]: continue if new_nums[i]0 and new_nums[i1]0: break lefti1 rightlength-1 while leftright: sumsnew_nums[i]new_nums[left]new_nums[right] if sums0: result.append([new_nums[i],new_nums[left],new_nums[right]]) left1 while leftright and new_nums[left-1]new_nums[left]: left1 right-1 elif sums0: right-1 else: left1由此循环即可得出最终三元组数组并返回。完整代码如下class Solution(object): def threeSum(self, nums): :type nums: List[int] :rtype: List[List[int]] lengthlen(nums) # 长度等于3特殊情况 if length3: if sum(nums)0: return [nums] else: return [] # 对原数组进行排序得到升序排序的新数组 new_numssorted(nums) # 判断全为正数或全为负数的特殊情况 if new_nums[0]0 or new_nums[-1]0: return [] result[] # 对数组进行循环 for i in range(length-2): # 若i对应值与递增之前相同直接跳过 if i1: if new_nums[i]new_nums[i-1]: continue # 若后面全是正数直接结束循环 if new_nums[i]0 and new_nums[i1]0: break lefti1 rightlength-1 # 使用while循环移动左右指针 while leftright: sumsnew_nums[i]new_nums[left]new_nums[right] if sums0: result.append([new_nums[i],new_nums[left],new_nums[right]]) left1 # 判断后面数是否与前数重复 while leftright and new_nums[left-1]new_nums[left]: left1 right-1 elif sums0: right-1 else: left1 return result
