前段时间，我们在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，演示一下小灰的具体思路：第一轮，访问数组的第一个元素5，将问题转化为从后面的元素求8的和(13-5)两个数：如何找出和为8的两个数？按照我们上次说的，我们可以使用哈希表高效求解：第二轮，访问数组的第二个元素12，把问题转化为寻找和为1的两个数（13-12）从以下元素：第三轮，访问数组的第三个元素6，将问题转化为从以下元素求7的和（13-12）6）二数：以此类推，遍历整个数组相当于求解两个数的和n次。publicstaticList>threeSum(int[]nums,inttarget){List>resultList=newArrayList<>();for(inti=0;imap=newHashMap<>();intd1=target-nums[i];//求两个数之和等于d1的组合for(intj=i+1;j12，结果太大了。由于数组是升序排列的，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，将问题转化为从后面的元素中找出和为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向左移动：此时，双指针再次重合，结束本次循环。按照这个思路，我们一直在遍历整个数组。用两个指针分别指向数组的两端，不断向中间靠拢寻找匹配组合的方法就是双指针法，也称为“钳位法”。publicstaticList>threeSumv2(int[]nums,inttarget){Arrays.sort(nums);List>resultList=newArrayList>();//大循环for(inti=0;id){k--;}//双指针重合，跳出本循环if(j==k){break;}if(nums[j]+nums[k]==d){Listlist=Arrays.asList(nums[i],nums[j],nums[k]);resultList.add(list);}}}returnresultList;}上面的代码表面上三层循环，但是指针j的移动次数每轮k次加起来最多n-1次。所以这个解决方案的整体时间复杂度是O(n2)。最重要的是这个方案没有使用额外的集合（直接对输??入数组进行排序），所以空间复杂度仅为O(1)！按照下面的二维码进行操作。转载本文请联系程序员小灰公众号。
