文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-12-03 18:54

关注

前一段时间,我们介绍了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

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯