算法套路二:相向双指针
创始人
2024-05-29 16:46:58
0

算法套路二:相向双指针

算法套路示例讲解:LeetCode167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。
在这里插入图片描述
在这里插入图片描述

考虑相向双指针,若输入为[2,3,4,6,8],target为9,左指针 left = 0,右指针right = len(numbers) - 1
首先数组为2,3,4,6,8,此时左端点为2,右端点为8,相加为10>target=9,且由于是有序数组,左指针右边的数都比2大,故8与数组内任何数相加都大于target,所以8必不可能出现在答案中,故我们将右指针向左移动
此时我们数组为2 3 4 6,此时左端点为2,右端点为6,相加为8 此时数组为3 4 6,此时左端点为3,右端点为6,相加为9=target,故返回[left + 1, right + 1]

class Solution:def twoSum(self, numbers: List[int], target: int) -> List[int]:left = 0right = len(numbers) - 1while True:  # left < rights = numbers[left] + numbers[right]if s == target:return [left + 1, right + 1]if s > target:right -= 1else:left += 1

套路总结

比较 s = numbers[left] + numbers[right]与固定值target(关键为找到该固定值)
如果s > target,right--
如果s < target,left++

练习:LeetCode15. 三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
在这里插入图片描述
由题设i 三数之和为0,我们可以从0到nums[i-3]遍历每个数为最小的数字i,这样我们只用和上题一样,考虑数组[i+1,········]是否存在两个数等于-nums[i]。
注意不能重复,所以每次遍历i,j,k都判断是否与前一个数相同,相同则继续遍历。

func threeSum(nums []int) (ans [][]int) {sort.Ints(nums)n := len(nums)for i, x := range nums[:n-2] {if i > 0 && x == nums[i-1] { // 跳过重复数字continue}if x+nums[i+1]+nums[i+2] > 0 { // 优化一break}if x+nums[n-2]+nums[n-1] < 0 { // 优化二continue}j, k := i+1, n-1for j < k {s := x + nums[j] + nums[k]if s > 0 {k--} else if s < 0 {j++} else {ans = append(ans, []int{x, nums[j], nums[k]})for j++; j < k && nums[j] == nums[j-1]; j++ {} // 跳过重复数字for k--; k > j && nums[k] == nums[k+1]; k-- {} // 跳过重复数字}}}return
}

练习LeetCode16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在恰好一个解。在这里插入图片描述

与上题几乎一样,只是多了取差值,且不用考虑是否重复

func threeSumClosest(nums []int, target int) int {sort.Ints(nums)n := len(nums)best := math.MaxInt32// 根据差值的绝对值来更新答案update := func(cur int) {if abs(cur - target) < abs(best - target) {best = cur}}// 枚举 afor i := 0; i < n; i++ {// 保证和上一次枚举的元素不相等// 使用双指针枚举 b 和 cj, k := i + 1, n - 1for j < k {sum := nums[i] + nums[j] + nums[k]// 如果和为 target 直接返回答案if sum == target {return target}update(sum)if sum > target {// 如果和大于 target,移动 c 对应的指针k --} else {// 如果和小于 target,移动 b 对应的指针j++}}}return best
}
func abs(x int) int {if x < 0 {return -1 * x}; return x}

练习LeetCode18. 四数之和

给你一个由 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 你可以按 任意顺序 返回答案 。
在这里插入图片描述

func fourSum(nums []int, target int) [][]int {sort.Ints(nums)n:=len(nums)ans:=make([][]int ,0)if n<4{return ans}for a,numA:=range nums[:n-3]{if a>0&&numA==nums[a-1]{continue}for i := a + 1; i < len(nums) - 2; i++ {if i > a+1 && nums[i] == nums[i-1] { // 跳过重复数字continue}j, k := i+1, n-1for j < k {s := nums[i] + nums[j] + nums[k] + numAif s > target {k--} else if s < target {j++} else {ans = append(ans, []int{numA,nums[i], nums[j], nums[k]})for j++; j < k && nums[j] == nums[j-1]; j++ {} // 跳过重复数字for k--; k > j && nums[k] == nums[k+1]; k-- {} // 跳过重复数字}}}}return ans
}

进阶LeetCode611. 有效三角形的个数

给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。
在这里插入图片描述

最长边nums[k]为值target枚举,从而使判断条件为nums[l] + nums[r]>target

func triangleNumber(nums []int) int {sort.Ints(nums)var res int// 遍历第三条边,找前两条边之和大于第三条边的组合for k := len(nums)-1; k >= 2; k-- {l, r := 0, k - 1target:=nums[k]for l < r {if nums[l] + nums[r] >target {res += r-lr--} else {l++}}}return res
}

相关内容

热门资讯

安卓系统无法自己升级,自主升级... 你是不是也遇到了这个问题?安卓系统怎么就突然不升级了呢?别急,今天就来给你好好捋一捋这个让人头疼的小...
华为变成原生安卓系统,原生安卓... 你知道吗?最近科技圈可是炸开了锅,华为的大动作让所有人都瞪大了眼睛。没错,就是那个我们熟悉的华为,竟...
安卓系统手机很便宜,高性价比的... 你有没有发现,最近逛手机市场,安卓系统手机的价格真是让人惊喜不已呢!没错,就是那种我们平时用的最多的...
原生的安卓系统 索尼,深度解析... 你知道吗?在智能手机的世界里,有一个品牌总是以其独特的魅力和精湛的工艺吸引着众多科技爱好者。那就是索...
安卓系统更新历史,从初代到最新... 你有没有发现,你的安卓手机每次更新后都变得焕然一新?没错,这就是安卓系统更新带来的魔力!今天,就让我...
安卓系统的第二套系统,创新与变... 你知道吗?在科技飞速发展的今天,安卓系统已经成为了智能手机市场上的霸主。但是,你知道吗?安卓系统其实...
全军出击安卓系统版本,战力再攀... 你有没有发现,最近全军出击这款游戏在安卓系统上的版本更新可是越来越频繁了呢?这不,我就来给你好好扒一...
安卓系统热点限速软件,优化热点... 你有没有遇到过这种情况:手机连接热点后,网速就像蜗牛爬行一样慢,简直让人抓狂!别急,今天就来给你揭秘...
安卓系统占内存多,揭秘内存消耗... 你有没有发现,手机用着用着,内存就不够用了?尤其是安卓系统,好像特别能吃内存,让人头疼不已。今天,就...
最近安卓系统奔溃,揭秘原因与应... 最近手机界可是炸开了锅呢!安卓系统竟然出现了大规模奔溃,这可真是让人摸不着头脑。咱们一起来探究这背后...
ce系统能刷安卓系统吗,揭秘能... 你有没有想过,你的安卓手机是不是也能用上CE系统呢?这可不是天方夜谭,今天就来给你揭秘一下这个神秘的...
安卓系统UI设计特色,创新与用... 你有没有发现,每次打开安卓手机,那界面设计得真是让人眼前一亮呢?今天,就让我带你一起探索一下安卓系统...
ipod有安卓系统吗,跨界融合... 你有没有想过,那个曾经风靡一时的iPod,它到底有没有安卓系统呢?这个问题,估计让不少音乐爱好者都好...
安卓多少系统最高的,揭秘最高版... 你有没有想过,你的安卓手机到底升级到了哪个系统版本呢?是不是好奇安卓系统里哪个版本才是最高级的呢?别...
现在安卓最高的系统,揭秘安卓1... 你有没有发现,手机更新换代的速度简直就像坐上了火箭呢!这不,最近安卓系统又来了一次大升级,听说这是现...
安卓系统怎么隐藏相册,安卓系统... 你是不是也有那么几本“私人珍藏”,不想让旁人随意翻看呢?比如,手机里的相册,里面藏着我们的喜怒哀乐,...
安卓桌面挂件系统下载,下载与个... 你有没有发现,手机桌面上的那些小玩意儿,简直就是生活的调味品?今天,咱们就来聊聊安卓桌面挂件系统下载...
wp手机加安卓系统,探索跨界新... 你有没有想过,为什么你的手机总是那么卡,而别人的手机却流畅得像风一样?是不是觉得自己的手机有点OUT...
省电手机推荐安卓系统,安卓系统... 手机这玩意儿,对于我们这些手机控来说,简直就是生活的必需品。但是,你知道吗?现在市面上那么多手机,要...
安卓系统衰落怎么恢复,探寻衰落... 你有没有发现,最近安卓系统好像有点儿“水土不服”了呢?曾经的霸主地位,如今似乎有些动摇。不过别急,今...