三数之和问题

题目概述

给定一个数组，我们随意选定一个特定值，比如13，要求找出三数之和等于13的全部组合。

​

例如：

1+3+9=13，1+5+7=13，最终输出的结果如下（输出的是三个数的值）

[1,3,9]

[1,5,7] 

本来在这我是想使用哈希表的方法展示给大家看，但双指针相对于哈希表的方法在空间复杂度上，相对占有优势。所以本人在这选择了双指针的方法。

在这里使用双指针的前提，我们先要获得一个升序排列的数组。

​

记住由于该数组我们排列成升序，当两指针对应两元素之和小于要求的元素，我们将j指针右移动一位，否则将k指针向左移动一位。

第一轮，访问数组的第一个元素1，把问题转成从后面元素中找出和位12（13-1）的两个数。

如何找出和为12的数呢？我们设置两个指针，指针j指向剩余元素中最左边的元素2，指针k指向最右侧的元素12； 

计算两指针对应的元素之和，2+12>12,结果偏大。因此我们把指针k左移一位 

再计算两指针对应的元素之和，2+9<12结果偏小。因此我们把指针j向右移一位。 

 再计算两指针对应元素之和，3+9=12，正好符合要求！

因此我们成功找到一组匹配的组合：1，3，9。   然后我们再让指针k左移一位。 

再计算两指针对应的元素之和，3+7<12结果偏小。因此我们把指针j向右移一位。 

 再计算两指针对应元素之和，5+7=12，正好符合要求！ 继续将k指针左移。

 再计算两指针对应的元素之和，5+6<12结果偏小。因此我们把指针j向右移一位。 

 此时双指针重合在一起，如果再继续移动，就有可能和之前找到的组合重复，因此我们结束本轮循环。

第2轮，访问数组的第二个元素2，把问题转成从后面元素中找出和位11（13-2）的两个数。

我们仍然设置两个指针 ，指针j指向剩余元素中最左边的元素3，指针k指向最右侧的元素12； 

计算两指针对应的元素之和，3+12>11,结果偏大。因此我们把指针k左移一位  

再计算两指针对应的元素之和，3+9>11,结果偏大。因此我们把指针k左移一位 

 再计算两指针对应的元素之和，3+7<11,结果偏小。因此我们把指针j右移一位 

再计算两指针对应的元素之和，5+7>11,结果偏大。因此我们把指针k左移一位  

  再计算两指针对应元素之和，5+6=11，正好符合要求！ 继续将k指针左移。

 此时双指针又一次重合在一起，我们结束本轮循环。

按照这个思路，我们一直遍历完整个数组。

像这种利用两指针指向数组两端，不断向中间靠拢调整来寻找匹配组合的方法，就是双指针法，也被称为"夹逼法"。

主要方法的实现

  public static List> threeSumV(int[] nums,int target){Arrays.sort(nums);List> resultList=new ArrayList>();for(int i=0;id){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;}

 代码实现：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class Demo {public static void main(String[] args) {Scanner sc=new Scanner(System.in);System.out.println("请输入三数之和：");int target=Integer.parseInt(sc.nextLine());int[] nums={5,12,6,3,9,2,1,7};List> resultList=threeSumV(nums,target);for(List list:resultList){for(Integer num:list){System.out.print(num+" ");}System.out.println();}}public static List> threeSumV(int[] nums,int target){Arrays.sort(nums);List> resultList=new ArrayList>();for(int i=0;id){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;}
}

搞定！

不过大家也别太高兴了，使用以上方法只是应用没有重复元素的数组，

活动地址：CSDN21天学习挑战赛

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！