在数组中寻找和为指定值的两个数

爱被打了一巴掌 2022-08-27 05:37 161阅读 0赞

**题目：在数组中寻找和为指定值的两个数，如arr=\{1, 2,3,4,7,8\} ，指定值sum为12，返回4+8=12**

方法1：

采用暴力破解（即穷举），时间复杂度为O(n\*n)，即对每一个数arr\[i\]，搜索sum-arr\[i\]在不在数组中。

方法2：

根据方法1，如果数组已经排好序，可以使用二分查找sum-arr\[i\]；如果没有排好序可以使用某种排序算法对其先进行排序（如平均复杂度为nlogn的快排（取决于划分元的选择，可以选取第一个，或者第一个和中间元素和最后一个的中位数，或者随机选取，或者按照BFPRT算法那样选取等），nlogn的堆排序或者归并排序等）。时间复杂度为nlogn。

方法3：

可以采用Hash表存储，对于每一个元素arr\[i\]，在Hash表中查找sum-arr\[j\]是否存在，因为Hash查找的时间复杂度为O(1)，所以期望的时间复杂度为O(n)，但是因为Hash表空间有限，所以会产生冲突，解决冲突的方法有链表法和开放地址法等，比如链表法在极端情况下，所有元素都存在一个链中，那么就退化为O(n\*n），这取决于Hash函数与Hash表的空间大小。这是典型的用空间换取时间。

方法4：

如果只是数组中最多存在一对这样的数，便可以采取下面的方法：

比如arr=\{1,2,3,4,7,8\}，sum=12

首先求得sum-arr=\{11,10,9,8,5,4\}

然后定义两个索引标号i与j，i从arr头开始向后移动，j从sum-arr尾开始向前移动，哪个指向的元素小，就先移动到大于等于另一个指向的元素，如果两个指向的元素相等，则选出该元素，继续移动，直到到达边界。选中的两个元素便是结果，如果选出的元素个数小于2则该数组中没有符合条件的。但是该方法有个缺陷，如果含有多对符合条件的元素对，那么最后要从选出的结果中继续寻找。

方法5：

如果数组是无序的，则可以先进行排序（nlogn）。然后定义两个索引标号i与j，分别指向排序后的数组的头和尾，然后i向后移动（++i)，j向前移动(++j)，到i>=j则停止。

如果arr\[i\]+arr\[j\]=sum，则找到了一对，然后++i和++j，继续寻找；

如果arr\[i\]+arr\[j\]>sum，则--j；

如果arr\[i\]+arr\[j\]<sum，则++i；

到i>=j则停止。

时间复杂度为O(n)。

发表评论取消回复

表情：

评论列表（有 0 条评论，161人围观）

还没有评论，来说两句吧...

相关阅读

相关两数和问题（在数组中找出两数和为给定整数的两元素）

题目：输入包含n个整数是数组A的整数x,求出满足A\[i\]+A\[j\]=x的i和j，如果没有这样的元素和，则返回-1和-1。我的分析如下：此题需要注意的是

超、凢脫俗/ 2023年07月12日 14:20/ 0 赞/ 14 阅读

相关 LeetCode 数组中两个数的最大异或值

题目链接：[https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/][https_le

迷南。/ 2023年06月04日 14:56/ 0 赞/ 49 阅读

相关 421. 数组中两个数的最大异或值

链接：[https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/][https_leet

左手的ㄟ右手/ 2022年10月15日 10:53/ 0 赞/ 175 阅读

相关快速寻找满足条件的两个数

时间：2014.07.17 地点：基地 \-----------------------------------------------------------------

Myth丶恋晨/ 2022年08月27日 15:37/ 0 赞/ 169 阅读

相关在数组中寻找和为指定值的两个数

题目：在数组中寻找和为指定值的两个数，如arr=\{1, 2,3,4,7,8\} ，指定值sum为12，返回4+8=12 方法1：采用暴力破解（即穷举），时间复杂度为O(

爱被打了一巴掌/ 2022年08月27日 05:37/ 0 赞/ 162 阅读

相关寻找和为定值的多个数

输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数, 使其和等于 m ,要求将其中所有的可能组合列出来。两种方法，其实本质都是递归算法结构

小咪咪/ 2022年08月07日 13:59/ 0 赞/ 120 阅读

相关寻找和为定值的两个数

寻找和为定值的两个数 1. 题目描述给定一个数组（无序或者有序，两种情况都要考虑），找出和为M的两个数。最多时间复杂度能有多少？ https:

比眉伴天荒/ 2022年08月06日 00:23/ 0 赞/ 145 阅读

相关找出数组中两数之和为指定值的所有整数对

定一个整型数组（数组中的元素可重复，已排序），以及一个指定的值。找出数组中两数之和为指定值的所有整数对，要求时间复杂度为O(N)。首先来分析一下这个题，假设题目没

左手的ㄟ右手/ 2021年12月18日 06:45/ 0 赞/ 250 阅读

相关寻找和为定值的多个数

编程求解：输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数, 使其和等于 m ,要求将其中所有的可能组合列出来。 // 寻求和为

小鱼儿/ 2021年11月15日 13:18/ 0 赞/ 226 阅读

相关 LeetCode||两数之和--给定一个数组和一个目标值，找出数组中和为目标值的两个数

题目描述：给定一个数组和一个目标值，找出数组中和为目标值的两个数。假设每个输入只对应一种答案，而且同样的元素不能重复利用。示例：给定nums = \[2,7

迈不过友情╰/ 2021年11月09日 20:32/ 0 赞/ 306 阅读