如何在数组中找到和为“特定值”的三个数？程序员小灰尝试在数组中找到

程序员小灰
尝试在数组中找到和为“特定值”的三个数。
题目的具体要求是什么呢？给定下面这样一个整型数组：
文章插图
我们随意选择一个特定值，比如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（n2）。
至于空间复杂度，同一个哈希表被反复构建，哈希表中最多有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继续左移：
文章插图