我的编程空间,编程开发者的网络收藏夹
学习永远不晚

如何在数组中找到和为 “特定值” 的三个数?

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

如何在数组中找到和为 “特定值” 的三个数?

前一段时间,我们介绍了LeetCode上面的一个经典算法题【两数之和问题】。

这一次,我们把问题做一下扩展,尝试在数组中找到和为“特定值”的三个数。

题目的具体要求是什么呢?给定下面这样一个整型数组:

 

我们随意选择一个特定值,比如13,要求找出三数之和等于13的全部组合。

由于5+6+2=13, 5+1+7=13,3+9+1=13,所以最终的输出结果如下:

【5, 6,2】

【5, 1,7】

【3, 9,1】

 

小灰的思路,是把原本的“三数之和问题”,转化成求n次“两数之和问题”。

 

我们以上面这个数组为例,选择特定值13,演示一下小灰的具体思路:

第1轮,访问数组的第1个元素5,把问题转化成从后面元素中找出和为8(13-5)的两个数:

 

如何找出和为8的两个数呢?按照上一次所讲的,我们可以使用哈希表高效求解:

 

第2轮,访问数组的第2个元素12,把问题转化成从后面元素中找出和为1(13-12)的两个数:

 

第3轮,访问数组的第3个元素6,把问题转化成从后面元素中找出和为7(13-6)的两个数:

 

以此类推,一直遍历完整个数组,相当于求解了n次两数之和问题。

 

 

  1. public static ListInteger>> threeSum(int[] nums, int target) { 
  2.        ListInteger>> resultList = new ArrayList<>(); 
  3.        for (int i = 0; i < nums.length; i++) { 
  4.            Map<IntegerInteger> map = new HashMap<>(); 
  5.            int d1 = target - nums[i]; 
  6.            //寻找两数之和等于d1的组合 
  7.            for (int j = i+1; j < nums.length; j++) { 
  8.                int d2 = d1 - nums[j]; 
  9.                if (map.containsKey(d2)) { 
  10.                    resultList.add(Arrays.asList(nums[i], d2, nums[j])); 
  11.                } 
  12.                map.put(nums[j], j); 
  13.            } 
  14.        } 
  15.        return resultList; 
  16.    } 

在上面的代码中,每一轮解决“两数之和问题”的时间复杂度是O(n),一共迭代n轮,所以该解法总的时间复杂度是O(n²)。

至于空间复杂度,同一个哈希表被反复构建,哈希表中最多有n-1个键值对,所以该解法的空间复杂度是O(n)。

 

我们仍然以之前的数组为例,对数组进行升序排列:

 

这样说起来有些抽象,我们来具体演示一下:

第1轮,访问数组的第1个元素1,把问题转化成从后面元素中找出和为12(13-1)的两个数。

如何找出和为12的两个数呢?我们设置两个指针,指针j指向剩余元素中最左侧的元素2,指针k指向最右侧的元素12:

 

计算两指针对应元素之和,2+12 = 14 > 12,结果偏大了。

由于数组是按照升序排列,k左侧的元素一定小于k,因此我们把指针k左移一位:

 

计算两指针对应元素之和,2+9 = 11< 12,这次结果又偏小了。

j右侧的元素一定大于j,因此我们把指针j右移一位:

 

计算两指针对应元素之和,3+9 = 12,正好符合要求!

因此我们成功找到了一组匹配的组合:1,3,9

但这并不是结束,我们要继续寻找其他组合,让指针k继续左移:

 

计算两指针对应元素之和,3+7 = 10< 12,结果偏小了。

于是我们让指针j右移:

 

计算两指针对应元素之和,5+7 = 12,又找到符合要求的一组:

1,5,7

我们继续寻找,让指针k左移:

 

计算两指针对应元素之和,5+6 = 11< 12,结果偏小了。

于是我们让指针j右移:

 

此时双指针重合在了一起,如果再继续移动,就有可能和之前找到的组合重复,因此我们直接结束本轮循环。

第2轮,访问数组的第2个元素2,把问题转化成从后面元素中找出和为11(13-2)的两个数。

我们仍然设置两个指针,指针j指向剩余元素中最左侧的元素3,指针k指向最右侧的元素12:

 

计算两指针对应元素之和,3+12 = 15 > 11,结果偏大了。

我们让指针k左移:

 

计算两指针对应元素之和,3+9 = 12 > 11,结果仍然偏大。

我们让指针k继续左移:

 

计算两指针对应元素之和,3+7 = 10 < 11,结果偏小了。

我们让指针j右移:

 

计算两指针对应元素之和,5+7 = 12 > 11,结果又偏大了。

我们让指针k左移:

 

计算两指针对应元素之和,5+6 = 11,于是我们又找到符合要求的一组:

2,5,6

我们继续寻找,让指针k左移:

 

此时双指针又一次重合在一起,我们结束本轮循环。

按照这个思路,我们一直遍历完整个数组。

像这样利用两个指针指向数组两端,不断向中间靠拢调整来寻找匹配组合的方法,就是双指针法,也被称为“夹逼法”。

 

 

  1. public static ListInteger>> threeSumv2(int[] nums, int target) { 
  2.     Arrays.sort(nums); 
  3.     ListInteger>> resultList = new ArrayListInteger>>(); 
  4.     //大循环 
  5.     for (int i = 0; i < nums.length; i++) { 
  6.         int d = target - nums[i]; 
  7.         // j和k双指针循环定位,j在左端,k在右端 
  8.         for (int j=i+1,k=nums.length-1; j
  9.             // k指针向左移动 
  10.             while (jd) { 
  11.                 k--; 
  12.             } 
  13.             //双指针重合,跳出本次循环 
  14.             if (j == k) { 
  15.                 break; 
  16.             } 
  17.             if (nums[j] + nums[k] == d) { 
  18.                 List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]); 
  19.                 resultList.add(list); 
  20.             } 
  21.         } 
  22.     } 
  23.     return resultList; 

上面这段代码表面上有三层循环,但每一轮指针j和k的移动次数加起来最多n-1次,因此该解法的整体时间复杂度是O(n²)。

最关键的是,该解法并没有使用额外的集合(排序是直接在输入数组上进行的),所以空间复杂度只有O(1)!

本文转载自微信公众号「程序员小灰」,可以通过以下二维码关注。转载本文请联系程序员小灰公众号。

 

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

如何在数组中找到和为 “特定值” 的三个数?

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

如何在数组中找到和为 “特定值” 的三个数?

前一段时间,我们介绍了LeetCode上面的一个经典算法题【两数之和问题】。这一次,我们把问题做一下扩展,尝试在数组中找到和为“特定值”的三个数。

在 Java 中如何删除数组的某个特定值?(java中怎么删除数组的某个值)

在Java编程中,数组是一种常用的数据结构,用于存储相同类型的元素。有时候,我们需要删除数组中的某个特定值。本文将介绍在Java中如何删除数组的某个值,分为以下两个主要步骤:一、查找要删除的值的索引在删除数组中的某个值之
在 Java 中如何删除数组的某个特定值?(java中怎么删除数组的某个值)
Java2024-12-23

如何用PHP移除数组中特定的键值对

这篇文章主要介绍了如何用PHP移除数组中特定的键值对的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇如何用PHP移除数组中特定的键值对文章都会有所收获,下面我们一起来看看吧。方法一:使用unset()函数移除指定
2023-07-05

python 如何在list中找Topk的数值和索引

需求: 对于一个python list 或者numpy数组,我需要找到这个list中最大的K个数及其对应的下标。 解决方式: 1. 可以构造字典通过排序解决,不过代码量较多。 2. 使用heapq库,可以直接获取最大值的下标和数值。impo
2022-06-02

如何在 PHP 中根据特定键值对去除数组中的重复项?

在 php 中,使用 array_unique() 函数,根据特定键值对去除数组重复项。调用函数时传入数组作为参数,选择排序方式作为第二个参数。此函数返回一个新数组,其中重复项已根据指定的键值对被移除。如何在 PHP 中根据特定键值对去除数
如何在 PHP 中根据特定键值对去除数组中的重复项?
2024-04-28

php如何获取数值在数组中的哪个位置

这篇“php如何获取数值在数组中的哪个位置”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“php如何获取数值在数组中的哪个位置
2023-06-30

Java和C++如何在排序数组中查找数字出现的次数

这篇文章主要介绍“Java和C++如何在排序数组中查找数字出现的次数”,在日常操作中,相信很多人在Java和C++如何在排序数组中查找数字出现的次数问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java和C+
2023-06-21

jQuery如何使用特定名字的元素对应的值生成一个数组

这篇文章主要为大家展示了“jQuery如何使用特定名字的元素对应的值生成一个数组”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“jQuery如何使用特定名字的元素对应的值生成一个数组”这篇文章吧。
2023-06-27

在 Java 中如何给两个数组赋予相同的值?(Java中怎么给两个数组赋予一样的值)

在Java编程中,给两个数组赋予相同的值是一个常见的需求。以下是详细的步骤和示例代码来实现这一目标。一、理解数组的基本概念数组是一种用于存储相同类型数据的容器。在Java中,数组的长度是固定的,一旦创建就不能改变。数组的
在 Java 中如何给两个数组赋予相同的值?(Java中怎么给两个数组赋予一样的值)
Java2024-12-16

如何在golang中将切片的长度定义为数组?

在Golang中,切片与数组是两种不同的数据类型。切片是一个动态长度的序列,而数组是一个固定长度的序列。如果你想将切片的长度定义为数组,可以通过创建一个固定长度的数组,然后使用切片来引用该数组来实现。具体操作是先创建一个指定长度的数组,然后
如何在golang中将切片的长度定义为数组?
2024-02-08

如何用JS判断数组中是否存在某个值或者某个对象的值

数组是我们编程中经常使用的的数据结构之一,在处理数组时,我们经常需要在数组中查找特定的值,下面这篇文章主要给大家介绍了关于如何用JS判断数组中是否存在某个值或者某个对象的值的相关资料,需要的朋友可以参考下
2023-01-17

C++如何实现在有序数组中查找元素的第一个和最后一个位置

这篇文章主要讲解了“C++如何实现在有序数组中查找元素的第一个和最后一个位置”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++如何实现在有序数组中查找元素的第一个和最后一个位置”吧!Fin
2023-06-20

PHP如何在数组中搜索给定的值,如果成功则返回首个相应的键名

PHP提供了多种在数组中搜索给定值的方法,包括:in_array():返回true(如果值在数组中)或false(如果值不在数组中)array_search():如果值在数组中,返回第一个匹配键的名称,否则返回falsearray_keys():返回数组中所有键名的数组array_values():返回数组中所有值的数组对于大型数组,in_array()比array_search()更有效,因为它使用内部散列表进行查找。
PHP如何在数组中搜索给定的值,如果成功则返回首个相应的键名
2024-04-02

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录