首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

为什么3sum算法只查看特定数字右侧的子数组?

3Sum 算法是一种解决数组中和为特定值的问题,通常用于查找数组中所有唯一的三元组,使得它们的和等于给定的目标值。在实现 3Sum 算法时,有时会选择只查看特定数字右侧的子数组,这是出于优化时间和空间复杂度的考虑。

基础概念

3Sum 算法的核心思想是通过双指针法来减少不必要的计算。基本步骤如下:

  1. 排序:首先对数组进行排序。
  2. 遍历:遍历数组中的每一个元素,将其作为三元组的第一个元素。
  3. 双指针:对于每一个固定的第一个元素,使用双指针法在其右侧的子数组中查找另外两个元素,使得它们的和等于目标值减去第一个元素的值。

为什么只查看特定数字右侧的子数组?

  1. 避免重复:通过固定一个元素并只在其右侧查找,可以避免重复的三元组。例如,如果数组中有 [1, 2, -3, 3, 1],固定 1 后,在其右侧查找 2-3,而不是再次查找 12
  2. 时间复杂度优化:双指针法的时间复杂度是 O(n^2),相比于暴力搜索的 O(n^3),这种方法大大减少了计算量。
  3. 空间复杂度优化:由于不需要额外的存储空间来存储中间结果,空间复杂度为 O(1)。

类型

3Sum 算法主要分为两种类型:

  1. 3Sum:查找数组中所有和为 0 的三元组。
  2. k-Sum:一般化问题,查找数组中所有和为特定值的 k 个元素组合。

应用场景

3Sum 算法广泛应用于各种需要查找特定和的组合的场景,例如:

  • 数据分析:在金融数据分析中查找特定交易组合。
  • 算法竞赛:在编程竞赛中解决相关问题。
  • 软件测试:在测试用例生成中查找特定条件的组合。

示例代码

以下是一个简单的 3Sum 算法的实现示例:

代码语言:txt
复制
def three_sum(nums, target):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1
    
    return result

# 示例用法
nums = [-1, 0, 1, 2, -1, -4]
target = 0
print(three_sum(nums, target))

参考链接

3Sum 算法详解

通过上述解释和示例代码,希望你能更好地理解 3Sum 算法为什么只查看特定数字右侧的子数组,以及其背后的优化原理和应用场景。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

相关题目汇总分析总结

,从中找出两个数下标,使得它们和等于一个特定数字。...3Sum 从一个数组中找到三个数,使这三个数和为0。有可能存在多组解,也有可能存在重复解,所以需要去重。...3Sum Closest 3sum问题变种,寻找与目标数字最近那一组数,返回三数之和。假设题目有唯一解。...对排好序list去重,输出去重后长度,并且不能创建新数组 在 Remove Duplicates from Sorted Array(从一个有序数组中去除重复数字,返回处理后数组长度...Substring with Concatenation of All Words/与所有单词相关联字串 难题 现有一组长度相等字符串words,要在原字符串中找出正好包含words中所有字符串字符串起始位置

68710

15. 三数之和

想要找出三个数相加等于0,我们可以数组依次遍历, 每一项a[i]我们都认为它是最终能够用组成0中一个数字,那么我们目标就是找到 剩下元素(除a[i]) 两个相加等于-a[i]....通过上面的思路,我们问题转化为了 给定一个数组,找出其中两个相加等于给定值, 这个问题是比较简单, 我们只需要对数组进行排序,然后双指针解决即可。...加上我们需要外层遍历依次数组,因此总时间复杂度应该是O(N^2)。 思路如图所示: ?...在这里之所以要排序解决是因为, 我们算法瓶颈在这里不在于排序,而在于O(N^2),如果我们瓶颈是排序,就可以考虑别的方式了 如果找某一个特定元素,一个指针就够了。...如果是找两个元素满足一定关系(比如求和等于特定值),需要双指针, 当然前提是数组有序。

46030
  • 开篇!求和问题总结:2Sum3Sum4SumKSum

    算法重要性我在秋招总结文章中也提到了:算法和数据结构主要是以复习剑指offer和Leetcode原题为主。 在面试中,更多是考察你思路。而在线笔试中,就是比拼真刀真枪码代码比拼了。...,使得这K个数字和等于target。...方法二:哈希表 思路 复杂度分析: 时间复杂度:O(n), 我们遍历了包含有 n 个元素列表一次。在表中进行每次查找花费 O(1) 时间。...:三数之和 https://leetcode-cn.com/problems/3sum/ 题目大意 从一个数组中找到三个数,使这三个数和为0。.../ 题目大意 3sum问题变种,寻找与目标数字最近那一组数,返回三数之和 解题思路 方法一:双指针 思路 一样遍历每个数,对剩余数组进行双指针扫描。

    1.7K30

    一个函数秒杀 2Sum 3Sum 4Sum 问题

    请你返回 nums 中能够凑出 target 两个元素值,比如输入 nums = [5,3,1,6], target = 9,那么算法返回两个元素 [3,6]。...twoSum 函数就写出来了,请确保你理解了该算法逻辑,我们后面解决 3Sum 和 4Sum 时候会复用这个函数。...现在我们想找和为 target 三个数字,那么对于第一个数字,可能是什么?nums 中每一个元素 nums[i] 都有可能! 那么,确定了第一个数字之后,剩下两个数字可以是什么呢?...:穷举第一个数字,然后调用 3Sum 函数计算剩下三个数,最后组合出和为 target 四元组。...在 LeetCode 上,4Sum 就到头了,但是回想刚才写 3Sum 和 4Sum 过程,实际上是遵循相同模式

    71910

    015. 三数之和 | Leetcode题解

    0 中一个数字,那么我们目标就是找到剩下元素(除 a[i])两个相加等于-a[i]....这个问题是比较简单, 我们只需要对数组进行排序,然后双指针解决即可。加上需要外层遍历依次数组,因此总时间复杂度应该是 O(N^2)。 思路如图所示: ?...15.3-sum 在这里之所以要排序解决是因为, 我们算法瓶颈在这里不在于排序,而在于 O(N^2),如果我们瓶颈是排序,就可以考虑别的方式了。...思路2 标签:数组遍历 首先对数组进行排序,排序后固定一个数 nums[i]nums[i]nums[i],再使用左右指针指向 nums[i]nums[i]nums[i]后面的两端,数字分别为 nums[...关键点解析 排序之后,用双指针 分治 复杂度分析 时间复杂度: 空间复杂度:取决于排序算法空间消耗 代码 JavaScript 实现 /** * @来源:Javascript中文网 - 前端进阶资源教程

    41020

    923. 3Sum With Multiplicity 三数之和多种情况

    提示: 3 <= A.length <= 3000 0 <= A[i] <= 100 0 <= target <= 300 这道题是之前那道 3Sum 拓展,之前那道题是说没有重复数字,而这道题却有大量重复数字...因为有很多重复数字,所以将相同数字放在一起便于统计,可以对数组进行排序,然后遍历数组,先确定一个数字 A[i],则只需要找另外两个数字,使得其和为 sum = target-A[i]。...,还是使用一个 HashMap 建立数字跟其出现次数之间映射,但是这里并不是建立原数组每个数字跟其出现次数之间映射,而是建立数组中任意两个数字之和出现次数映射,该数字之和出现了几次,就说明有多少个不同两个数组合...那么此时遍历每个数字 A[i],将 numCnt[target-A[i]] 加入结果中,因为和为 target-A[i] 每个双数组合跟 A[i] 一起都可以组成符合题意数组合。...dp 数组,其中 dp[i][j][k] 表示在范围 [0, i] 内数组使用k个数字能组成和为j组合个数,则 dp[n][target][3] 即为所求,将 dp[i][0][0] 初始化为1。

    54130

    快速排序JavaScript实现详解

    排序是指以特定顺序(数字或字母)排列线性表元素。排序通常与搜索一起配合使用。 有许多排序算法,而迄今为止最快算法之一是快速排序(Quicksort)。...快速排序用分治策略对给定列表元素进行排序。这意味着算法将问题分解为问题,直到问题变得足够简单可以直接解决为止。 从算法上讲,这可以用递归或循环实现。但是对于这个问题,用递归法更为自然。...黑色粗体边框数组表示该特定递归分支结束时样子,最后得到数组包含一个元素。 最后可以看到该算法结果排序。 用 JavaScript 实现快速排序 这一算法主干是“分区”步骤。...我们需要一种跟踪剩下未排序数组方法。一种方法是简单地把“成对”元素保留在堆栈中,用来表示给定未排序数组 start 和 end。...stack.push(pivotIndex - 1); } // 如果基准右侧有未排序元素, // 则将该数组添加到栈中,以便稍后对其进行排序

    3.3K40

    前端学数据结构与算法(十二):有趣算法 - 多指针与滑动窗口

    前言 如果说如何用算法高效有趣解决某些问题,那多指针和滑动算法绝对是算其中佼佼者。.../leetcode-cn.com/problems/3sum 很容易想到就是暴力解,使用三层遍历,将三个数字累加和可能性都计算一遍,提取需要组合即可,暴力解复杂度是O(n³)。...如果这题是要返回它们对应下标,那还真没办法,不过既然是返回组合数字,那我们就可以利用有序数组特性,还是使用对撞指针更有效率解决此题。...如果不存在符合条件数组,返回 0。 输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 解释:数组 [4,3] 是该条件下长度最小数组。...当找到一个连续数组后,让左侧窗口向右滑动,减去最左侧值,减小窗口内和,也让窗口右侧滑动。如果又找到了一个满足条件数组,与之前数组长度进行比较,更新最小窗口大小即可。

    57010

    3Sum Closest「建议收藏」

    题意: 给定一个包括n个整数数组S,在数组中找出三个整数。使得这三个整数和与目标值最为接近。 返回这三个整数和。你能够假定对于每一个整数。都有确定一个解。...算法分析: 參考博客:http://www.zhuangjingyang.com/leetcode-3sum/ 和3Sum异曲同工。...只是这里我们要推断条件不在是三个数字和为0而是和为一个更加接近target数字。...我们依旧採用3Sum算法,若有三个数字x1 + x2 + x3 = result 我们所求便是让result最接近target。 因此对于num,首先排序。...然后遍历每一个数字其下标大于自身两个数字。然后设置两个全局变量 一个 minVal 用于记录其与target距离,当距离减小时便更新result新值。

    21510

    日拱算法:双指针解“压缩字符串”

    「这是我参与2022首次更文挑战第12天,活动详情查看:2022首次更文挑战」 ---- 日拱算法,日掘一金。...请在 修改完输入数组后 ,返回该数组新长度。 你必须设计并实现一个使用常量额外空间算法来解决此问题。...注意每个数字数组中都有它自己位置。 解题思路: 为了实现原地压缩,我们可以使用双指针分别标志我们在字符串中读和写位置。...每次当读指针 read 移动到某一段连续相同右侧,我们就在写指针 write 处依次写入该串对应字符和串长度即可。...在实际代码中,当读指针 read 位于字符串末尾,或读指针 read 指向字符不同于下一个字符时,我们就认为读指针 read 位于某一段连续相同右侧

    39430

    相关题目汇总分析总结

    N个数字(比如 vector num), 然后给你一个目标常数(比如 int target) ,我们目的是在这一堆数里面找到K个数字,使得这K个数字和等于target。...K Sum求解方法, 适用2Sum, 3Sum, 4Sum: 方法一: 暴力,就是枚举所有的K-subset, 那么这样复杂度就是 从N选出K个,复杂度是O(N^K),显然不会考察这种方法 方法二:...双指针,这个算法可以考虑最简单case, 2sum,这是个经典问题,方法就是先排序,然后利用头尾指针找到两个数使得他们和等于target,其他Ksum都是同样思路,只不过要固定前K-2个(利用循环...效率高 题目汇总 2Sum 3Sum 3Sum Closest 4Sum 总结 哈希表和双指针都是重要思路。...双指针方法大多需要排序,python中排序复杂度参考 时间复杂度对于上界O来说,永远是写最高,O(n log n)+ O(n^2)= O(n^2)

    1K30

    LeetCode 第一页题目

    Median of Two Sorted Arrays 给定两个排序整数数组,长度分别为m和n,求这两个数组所有数中位数,要求时间复杂度为O(log(m+n))。...在s中找出所有的下标i,满足s[i]开始串是由words中所有单词某种排列组成(所有单词有且出现出现一次)。...比如输入为:[3,4,-1,1],最小未出现正整数为:2 Jump Game II 给一个非负整数数组,每个数组元素表示你从该位置最多可以往前跳多少个位置,问从第一个位置跳到最后一个位置最少需要几跳...第一页其他题目,除开一些考察编码能力比较直接题目,有不少属于同类型题目,这样题目在面试中通常会作为一个问题延伸问题聊到,比如: 数组找几个数和为指定数问题:"Two Sum", "3Sum"...,一个题目可能会有不同时间/空间复杂度多种不同解法,有时候最优解算法也可能存在多种,这样题目也经常会在面试中使用以提高题目区分度。

    54110

    程序员进阶之算法练习(三十四)LeetCode专场

    前言 LeetCode上题目是大公司面试常见算法题,今天目标是拿下5道算法题: 1、2、3题都是Medium难度,大概是头条面试题水准; 4、5题是Hard难度,但是可以用取巧做法,实现难度降到...Medium和Easy难度; 正文 1、3Sum 题目链接 题目大意:给出一个数组nums,数组包括n个整数(可能有重复); 现在需要从数组中选择三个数a、b、c,使得a+b+c=0; 输出所有可能性组合...[-1, -1, 2] ] 题目解析: 题目可以分解为两个子问题: 1、找到整数a、b、c,使得a+b+c=0; 2、重复a、b、c输出一次; 问题1同样可以分解为两个问题:1、找到两个整数a、b...,判断c=-a-b数字是否存在; 那么可以用两个for循环确定a、b,再用一个for循环判断c=-a-b是否存在; 复杂度较高,但是可以解决,考虑问题2; 问题2可以通过缓存已经存在解,每次进行遍历匹配解决...k最大堆,然后遍历数组,把每个数字放进堆中,如果堆大小超过k,则弹出堆顶数字; 这样一轮过后,就有一个大小为k最大堆,堆顶就是第k大数字; 最后是一种理论(平均)最优解法,从数组中取第一个数字x

    90940

    LeetCode 16-20 题 详解 Java版 ( 万字 图文详解 LeetCode 算法题16-20 =====>>> <建议收藏>)

    解法二 受到上一题启发,没有看,推荐大家可以看一下。我们完全可以先将数组排序,然后先固定一个数字,然后利用头尾两个指针进行遍历,降低一个 O(n)时间复杂度。...总 和上一道题非常非常相似了,先对数组排序,然后利用两头指针,可以说是十分优雅了。 第17题....Letter Combinations of a Phone Number 题目描述(中等难度) 给一串数字,每个数可以代表数字键下几个字母,返回这些数字字母所有组成可能。...如果之前没有做过3Sum可以先看看,自己在上边基础上加了一个循环而已。...解法三 没看讲解前,和室友讨论下,如何遍历一次链表。室友给出了一个我竟然无法反驳观点,哈哈哈哈。

    9710

    二分查找应用---有序数组单一元素

    前言 大家好,我是程序员小熊,来自大厂程序猿。了解二分查找童鞋,都知道二分查找常用于在有序数组中查找某一特定元素,而且很多童鞋也都知道二分查找模板该怎么写。...题目 给定一个包含整数有序数组,每个元素都会出现两次,唯有一个数只会出现一次,找出这个数。...出现一次数字差不多,只是后者不要求数组是有序,但解法一样,可以通过异或去做,因为一个数字跟自身相异或,结果为 0;但异或 0,结果为自身,因此让数组中所有元素都相互异或即可得到结果,但时间复杂度为...),由于唯一那个数一定存在于奇数长度数组,因此丢弃偶数长度数组,在奇数长度数组中重复1和2; 3、若不等于两侧元素,则中间元素就是要查找出现一次那个数字。...3、判断拆分后数组长度,并移除偶数长度数组; ? 4、在奇数长度数组中重复前1、2、3步; ? 查找过程完整动态展示 动态如下: ?

    70560

    Java双端队列给定一个数组 nums,有一个大小为 k 滑动窗口从数组最左侧移动到数组右侧。你只可以看到在滑动窗口内 k 个数字。滑动窗口每次向右移动一位。 返回滑动窗口中最大值。

    双端队列实现 给定一个数组 nums,有一个大小为 k 滑动窗口从数组最左侧移动到数组右侧。你只可以看到在滑动窗口内 k 个数字。滑动窗口每次向右移动一位。...返回滑动窗口中最大值。...输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口位置 最大值 ----...5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 思路 : 1 开一个双端队列 和一个结果数组...,那么移除原来 } stack.addLast(i); //添加新进 if(stack.peekFirst()==i-k

    1.2K10

    算法细节系列(29):any sum

    https://blog.csdn.net/u014688145/article/details/72875071 算法细节系列(29):any sum 详细代码可以fork下Github...Leetcode 015. 3Sum 刚开始想法也是用一个MAP去存放所有的nums[i] + nums[j]组合,接着遍历一遍数组,去找和为key = 0 - nums[k]组合,时间复杂度能控制在...思路: 对数组进行排序,很关键,为了在搜索时,能把O(n2)O(n^2)复杂度降低到O(n)O(n) 把3sum问题归简为查找2sum问题。...(lf = i + 1,考虑i后面的元素) 这种while循环结构怎么就能确保找到了所有TWO SUM解。...第二个问题,它查找复杂度为O(n)O(n),原因在于数组有序,所以当: sum = nums[lf] + nums[rt]; 如果 sum < target 表明:nums[lf] + nums[rt

    33420
    领券