两数之和 三数之和【基础算法精讲 01】

两数之和 三数之和【基础算法精讲 01】学习B站灵茶山艾府的基础算法精讲 高频面试题合集之(两数之和 三数之和【基础算法精讲 01】)的总结167. 两数之和 II - 输入有序数组classSolution(object):deftwoSum(self,numbers,target): :type numbers: List[int] :type target: int :rtype: List[int] low,high0,len(numbers)-1whilelowhigh:sumnumbers[low]numbers[high]ifsumtarget:breakelifsumtarget:high-1else:low1returnlow1,high1核心思路双指针相向指针利用数组已升序排列的特性从两端向中间逼近15. 三数之和classSolution(object):defthreeSum(self,nums):# 思路使一个变量遍历整个数组剩余两个利用相向夹逼的方法# 前提是用排好序的数组,不用num num.sort()因为sort()本身就是对原数组进行操作nums.sort()nlen(nums)result[]foriinrange(n-2):# 去重跳过相同的 nums[i]ifi0andnums[i]nums[i-1]:continue# 剪枝最小三数之和 0后面都大breakifnums[i]nums[i1]nums[i2]0:break# 剪枝当前数 最大两个 0当前i不行continueifnums[i]nums[n-2]nums[n-1]0:continuelow,highi1,n-1whilelowhigh:totalnums[i]nums[low]nums[high]iftotal0:high-1eliftotal0:low1else:result.append([nums[i],nums[low],nums[high]])# 去重跳过相同的 lowwhilelowhighandnums[low]nums[low1]:low1# 去重跳过相同的 highwhilelowhighandnums[high]nums[high-1]:high-1# 移动到下一个不同的位置low1high-1returnresult小节一定要注意在符合sum 0 后移动lowhigh指针不然死循环还有range(n)是指0到n-1的数学习用while跳过相同的数达到去重。核心思路排序 固定一个 双指针2824. 统计和小于目标的下标对数目classSolution(object):defcountPairs(self,nums,target): :type nums: List[int] :type target: int :rtype: int nums.sort()countlow0highlen(nums)-1whilelowhigh:ifnums[low]nums[high]target:count(high-low)low1else:high-1returncount小节关键在于count (high-low)核心思路排序 双指针16. 最接近的三数之和classSolution(object):defthreeSumClosest(self,nums,target):nums.sort()nlen(nums)# 初始化直接用第一个三元组避免条件判断finsumnums[0]nums[1]nums[2]mindifffinsum-targetforiinrange(n-2):ifi0andnums[i]nums[i-1]:continuelow,highi1,n-1whilelowhigh:mysumnums[i]nums[low]nums[high]diffmysum-target# 更新最优解ifabs(diff)abs(mindiff):mindiffdiff finsummysum# 调整指针ifdiff0:high-1elifdiff0:low1else:returnmysum# 精确等于直接返回returnfinsum三数之和15最接近的三数之和16目标sum 0sum最接近target找到后记录所有组合继续找更新最优解继续逼近去重必须避免重复三元组可选不影响结果正确性返回所有满足条件的三元组列表一个最接近的整数18. 四数之和classSolution(object):deffourSum(self,nums,target): :type nums: List[int] :type target: int :rtype: List[List[int]] nums.sort()nlen(nums)ans[]foriinrange(n-3):ifi0andnums[i]nums[i-1]:continueforjinrange(i1,n-2):ifji1andnums[j]nums[j-1]:continuelowj1highn-1whilelowhigh:sumnums[i]nums[j]nums[low]nums[high]ifsumtarget:ans.append([nums[i],nums[j],nums[low],nums[high]])whilelowhighandnums[high]nums[high-1]:high-1whilelowhighandnums[low]nums[low1]:low1low1high-1elifsumtarget:high-1else:low1returnans# 增加优化classSolution(object):deffourSum(self,nums,target):nums.sort()nlen(nums)ans[]foriinrange(n-3):# 去重 iifi0andnums[i]nums[i-1]:continue# 剪枝最小四数和 target后面都大ifnums[i]nums[i1]nums[i2]nums[i3]target:break# 剪枝当前 i 最大三个 target当前 i 不行ifnums[i]nums[n-3]nums[n-2]nums[n-1]target:continueforjinrange(i1,n-2):# 去重 jifji1andnums[j]nums[j-1]:continue# 剪枝ifnums[i]nums[j]nums[j1]nums[j2]target:breakifnums[i]nums[j]nums[n-2]nums[n-1]target:continuelow,highj1,n-1whilelowhigh:totalnums[i]nums[j]nums[low]nums[high]iftotaltarget:ans.append([nums[i],nums[j],nums[low],nums[high]])# 去重 low跳过相同的whilelowhighandnums[low]nums[low1]:low1# 去重 high跳过相同的whilelowhighandnums[high]nums[high-1]:high-1# 移动到下一个不同的位置low1high-1eliftotaltarget:high-1else:low1returnans小节层级去重对象代码第一层固定的nums[i]重复if i 0 and nums[i] nums[i-1]: continue第二层固定的nums[j]重复if j i1 and nums[j] nums[j-1]: continue第三层low指针重复找到答案后while low high and nums[low] nums[low1]: low 1第四层high指针重复找到答案后while low high and nums[high] nums[high-1]: high - 1优化思路剪枝思路的核心在于利用数组有序性在固定外层循环元素时通过计算当前组合的理论最小和与最大和预判该分支是否可能包含有效解从而提前终止不可能的路径。具体而言当固定i后取i之后最小的三个元素求和若已大于target则说明后续更大的i只会让和更大直接break跳出循环反之取i之后最大的三个元素求和若仍小于target则当前i过小无论怎么组合都无法达到目标直接continue跳过。同理固定j后也进行相同的边界判断。这种先算边界再决定是否深入的策略将大量无效的双指针搜索扼杀在萌芽阶段在不漏解的前提下显著减少内层循环的执行次数是多数之和问题从能过到高效的关键优化。核心思路排序 双重循环固定两个 双指针611. 有效三角形的个数classSolution(object):deftriangleNumber(self,nums): :type nums: List[int] :rtype: int # 有效三角形任意两边和大于第三边# 逆向遍历有序数组让可移动的两个指针大于固定的指针nums.sort()nlen(nums)count0foriinrange(n-1,1,-1):# 剪枝ifnums[i]nums[i-1]nums[i-2]:continuelow0highi-1whilelowhigh:ifnums[low]nums[high]nums[i]:count(high-low)high-1elifnums[low]nums[high]nums[i]:low1returncount小节记忆口诀都不包括stop元素step为正start stop才执行从小到大step为负start stop才执行从大到小核心思路排序 固定最长边 双指针计数三角形判定条件任意两边之和大于第三边。数组排序后只需保证两条较小边之和 最大边即可。