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

程序员小灰
尝试在数组中找到和为“特定值”的三个数。
题目的具体要求是什么呢？给定下面这样一个整型数组：
文章插图
我们随意选择一个特定值，比如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）。
文章插图
文章插图
文章插图
文章插图
我们仍然以之前的数组为例，对数组进行升序排列：
文章插图