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

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

创新互联建站10多年成都企业网站建设服务;为您提供网站建设,网站制作,网页设计及高端网站定制服务,成都企业网站建设及推广,对塑料袋等多个领域拥有丰富的网站制作经验的网站建设公司。

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

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

我们随意选择一个特定值，比如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 List> threeSum(int[] nums, int target) {
    2. 
  
  
  
  
  2.        List> resultList = new ArrayList<>();
    3. 
  
  
  
  
  3.        for (int i = 0; i < nums.length; i++) {
    4. 
  
  
  
  
  4.            Map map = new HashMap<>();
    5. 
  
  
  
  
  5.            int d1 = target - nums[i];
    6. 
  
  
  
  
  6.            //寻找两数之和等于d1的组合
    7. 
  
  
  
  
  7.            for (int j = i+1; j < nums.length; j++) {
    8. 
  
  
  
  
  8.                int d2 = d1 - nums[j];
    9. 
  
  
  
  
  9.                if (map.containsKey(d2)) {
    10. 
  
  
  
  
  10.                    resultList.add(Arrays.asList(nums[i], d2, nums[j]));
    11. 
  
  
  
  
  11.                }
    12. 
  
  
  
  
  12.                map.put(nums[j], j);
    13. 
  
  
  
  
  13.            }
    14. 
  
  
  
  
  14.        }
    15. 
  
  
  
  
  15.        return resultList;
    16. 
  
  
  
  
  16.    }
    17.

在上面的代码中，每一轮解决“两数之和问题”的时间复杂度是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 List> threeSumv2(int[] nums, int target) {
    2. 
  
  
  
  
  2.     Arrays.sort(nums);
    3. 
  
  
  
  
  3.     List> resultList = new ArrayList>();
    4. 
  
  
  
  
  4.     //大循环
    5. 
  
  
  
  
  5.     for (int i = 0; i < nums.length; i++) {
    6. 
  
  
  
  
  6.         int d = target - nums[i];
    7. 
  
  
  
  
  7.         // j和k双指针循环定位，j在左端，k在右端
    8. 
  
  
  
  
  8.         for (int j=i+1,k=nums.length-1; j
  
  
  
  
  9.             // k指针向左移动
    10. 
  
  
  
  
  10.             while (jd) {
    11. 
  
  
  
  
  11.                 k--;
    12. 
  
  
  
  
  12.             }
    13. 
  
  
  
  
  13.             //双指针重合，跳出本次循环
    14. 
  
  
  
  
  14.             if (j == k) {
    15. 
  
  
  
  
  15.                 break;
    16. 
  
  
  
  
  16.             }
    17. 
  
  
  
  
  17.             if (nums[j] + nums[k] == d) {
    18. 
  
  
  
  
  18.                 List list = Arrays.asList(nums[i], nums[j], nums[k]);
    19. 
  
  
  
  
  19.                 resultList.add(list);
    20. 
  
  
  
  
  20.             }
    21. 
  
  
  
  
  21.         }
    22. 
  
  
  
  
  22.     }
    23. 
  
  
  
  
  23.     return resultList;
    24. 
  
  
  
  
  24. }
    25.

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

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

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

网站标题：如何在数组中找到和为“特定值”的三个数？
本文链接：http://www.hantingmc.com/qtweb/news25/273175.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

电子商务知识

行业网站建设

温江电信机房　　 　域名注册　　 　成都网站维护公司　　 　网站建设　　 　四川搅拌罐车　　 　重庆水土机房托管　　 　钢筋机械设备　　 　成都网站推广　　 　卡多尼人工智　　 　成都办公窗帘　　 　专业网站建设　　 　成都网站推广　　 　重庆手机网站建设　　 　企业网站建设　　 　seo优化排名　　 　腾讯免备案空间　　 　品牌网站建设　　 　四川國際商會　　 　重庆机房托管　　 　雅安服务器托管