两数之和 三数之和【基础算法精讲 01】
学习B站灵茶山艾府的基础算法精讲 高频面试题合集之
(两数之和 三数之和【基础算法精讲 01】)的总结
167. 两数之和 II - 输入有序数组
classSolution(object):deftwoSum(self,numbers,target):""" :type numbers: List[int] :type target: int :rtype: List[int] """low,high=0,len(numbers)-1whilelow<high:sum=numbers[low]+numbers[high]ifsum==target:breakelifsum>target:high-=1else:low+=1returnlow+1,high+1核心思路：双指针（相向指针）利用数组已升序排列的特性，从两端向中间逼近
15. 三数之和
classSolution(object):defthreeSum(self,nums):# 思路使一个变量遍历整个数组，剩余两个利用相向夹逼的方法# 前提是用排好序的数组,不用num = num.sort()，因为sort()本身就是对原数组进行操作nums.sort()n=len(nums)result=[]foriinrange(n-2):# 去重：跳过相同的 nums[i]ifi>0andnums[i]==nums[i-1]:continue# 剪枝：最小三数之和 > 0，后面都大，breakifnums[i]+nums[i+1]+nums[i+2]>0:break# 剪枝：当前数 + 最大两个 < 0，当前i不行，continueifnums[i]+nums[n-2]+nums[n-1]<0:continuelow,high=i+1,n-1whilelow<high:total=nums[i]+nums[low]+nums[high]iftotal>0:high-=1eliftotal<0:low+=1else:result.append([nums[i],nums[low],nums[high]])# 去重：跳过相同的 lowwhilelow<highandnums[low]==nums[low+1]:low+=1# 去重：跳过相同的 highwhilelow<highandnums[high]==nums[high-1]:high-=1# 移动到下一个不同的位置low+=1high-=1returnresult小节：一定要注意在符合sum == 0 后，移动low，high指针不然死循环；还有range(n)是指0到n-1的数；学习用while跳过相同的数达到去重。
核心思路：排序 + 固定一个 + 双指针
2824. 统计和小于目标的下标对数目
classSolution(object):defcountPairs(self,nums,target):""" :type nums: List[int] :type target: int :rtype: int """nums.sort()count=low=0high=len(nums)-1whilelow<high:ifnums[low]+nums[high]<target:count+=(high-low)low+=1else:high-=1returncount小节：关键在于count += (high-low)
核心思路：排序 + 双指针
16. 最接近的三数之和
classSolution(object):defthreeSumClosest(self,nums,target):nums.sort()n=len(nums)# 初始化：直接用第一个三元组，避免条件判断finsum=nums[0]+nums[1]+nums[2]mindiff=finsum-targetforiinrange(n-2):ifi>0andnums[i]==nums[i-1]:continuelow,high=i+1,n-1whilelow<high:mysum=nums[i]+nums[low]+nums[high]diff=mysum-target# 更新最优解ifabs(diff)<abs(mindiff):mindiff=diff finsum=mysum# 调整指针ifdiff>0:high-=1elifdiff<0:low+=1else:returnmysum# 精确等于，直接返回returnfinsum| 三数之和（15） | 最接近的三数之和（16） | |
|---|---|---|
| 目标 | sum == 0 | sum最接近target |
| 找到后 | 记录所有组合，继续找 | 更新最优解，继续逼近 |
| 去重 | 必须（避免重复三元组） | 可选（不影响结果正确性） |
| 返回 | 所有满足条件的三元组列表 | 一个最接近的整数 |
18. 四数之和
classSolution(object):deffourSum(self,nums,target):""" :type nums: List[int] :type target: int :rtype: List[List[int]] """nums.sort()n=len(nums)ans=[]foriinrange(n-3):ifi>0andnums[i]==nums[i-1]:continueforjinrange(i+1,n-2):ifj>i+1andnums[j]==nums[j-1]:continuelow=j+1high=n-1whilelow<high:sum=nums[i]+nums[j]+nums[low]+nums[high]ifsum==target:ans.append([nums[i],nums[j],nums[low],nums[high]])whilelow<highandnums[high]==nums[high-1]:high-=1whilelow<highandnums[low]==nums[low+1]:low+=1low+=1high-=1elifsum>target:high-=1else:low+=1returnans# 增加优化classSolution(object):deffourSum(self,nums,target):nums.sort()n=len(nums)ans=[]foriinrange(n-3):# 去重 iifi>0andnums[i]==nums[i-1]:continue# 剪枝：最小四数和 > target，后面都大ifnums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target:break# 剪枝：当前 i + 最大三个 < target，当前 i 不行ifnums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target:continueforjinrange(i+1,n-2):# 去重 jifj>i+1andnums[j]==nums[j-1]:continue# 剪枝ifnums[i]+nums[j]+nums[j+1]+nums[j+2]>target:breakifnums[i]+nums[j]+nums[n-2]+nums[n-1]<target:continuelow,high=j+1,n-1whilelow<high:total=nums[i]+nums[j]+nums[low]+nums[high]iftotal==target:ans.append([nums[i],nums[j],nums[low],nums[high]])# 去重 low：跳过相同的whilelow<highandnums[low]==nums[low+1]:low+=1# 去重 high：跳过相同的whilelow<highandnums[high]==nums[high-1]:high-=1# 移动到下一个不同的位置low+=1high-=1eliftotal>target:high-=1else:low+=1returnans小节：
| 层级 | 去重对象 | 代码 |
|---|---|---|
| 第一层 | 固定的nums[i]重复 | if i > 0 and nums[i] == nums[i-1]: continue |
| 第二层 | 固定的nums[j]重复 | if j > i+1 and nums[j] == nums[j-1]: continue |
| 第三层 | low指针重复 | 找到答案后，while low < high and nums[low] == nums[low+1]: 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()n=len(nums)count=0foriinrange(n-1,1,-1):# 剪枝ifnums[i]>nums[i-1]+nums[i-2]:continuelow=0high=i-1whilelow<high:ifnums[low]+nums[high]>nums[i]:count+=(high-low)high-=1elifnums[low]+nums[high]<=nums[i]:low+=1returncount小节：
记忆口诀：都不包括stop元素
step为正：start < stop才执行，从小到大
step为负：start > stop才执行，从大到小
核心思路：
排序 + 固定最长边 + 双指针计数
三角形判定条件：任意两边之和大于第三边。数组排序后，只需保证两条较小边之和 > 最大边即可。
