漫画：如何在数组中找到和为 “特定值” 的三个数？
扫描二维码
随时随地手机看文章
前一段时间，我们介绍了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次两数之和问题。
public static List> threeSum(int[] nums, int target) {
List> resultList = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
Map map = new HashMap<>();
int d1 = target - nums[i];
//寻找两数之和等于d1的组合
for (int j = i+1; j < nums.length; j++) {
int d2 = d1 - nums[j];
if (map.containsKey(d2)) {
resultList.add(Arrays.asList(nums[i], d2, nums[j]));
}
map.put(nums[j], j);
}
}
return resultList;
}
在上面的代码中，每一轮解决“两数之和问题”的时间复杂度是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左移：
此时双指针又一次重合在一起，我们结束本轮循环。
按照这个思路，我们一直遍历完整个数组。
像这样利用两个指针指向数组两端，不断向中间靠拢调整来寻找匹配组合的方法，就是双指针法，也被称为“夹逼法”。
public static List> threeSumv2(int[] nums, int target) {
Arrays.sort(nums);
List> resultList = new ArrayList>();
//大循环
for (int i = 0; i < nums.length; i++) {
int d = target - nums[i];
// j和k双指针循环定位，j在左端，k在右端
for (int j=i+1,k=nums.length-1; j // k指针向左移动
while (jd) {
k--;
}
//双指针重合，跳出本次循环
if (j == k) {
break;
}
if (nums[j] + nums[k] == d) {
List list = Arrays.asList(nums[i], nums[j], nums[k]);
resultList.add(list);
}
}
}
return resultList;
}
上面这段代码表面上有三层循环，但每一轮指针j和k的移动次数加起来最多n-1次，因此该解法的整体时间复杂度是O（n²）。
最关键的是，该解法并没有使用额外的集合（排序是直接在输入数组上进行的），所以空间复杂度只有O（1）！
—————END—————
喜欢本文的朋友，欢迎关注公众号 程序员小灰，收看更多精彩内容
点个[在看]，是对小灰最大的支持！
免责声明：本文内容由21ic获得授权后发布，版权归原作者所有，本平台仅提供信息存储服务。文章仅代表作者个人观点，不代表本平台立场，如有问题，请联系我们，谢谢！
下载文档
