2. 三数之和（数组、hashset）

思路及算法：

该题与第一题的“两数之和”相似，三数之和为0，不就是两数之和为第三个数的相反数吗？因为不能重复，所以，首先进行了一遍排序；其次，在枚举的时候判断了本次的第三个数的值是否与上一次的相同；再次，在寻找hashset时，判断当前的num[ j ]是否重复；最后，在枚举完一个第三个数之后，清空hashset。本题的答题思想与第一题类似，难度在于不可重复。

代码：

 1 Java：

 2 class Solution {

 3     public List<List<Integer>> threeSum(int [] nums) {

 4         //从小到大排序

 5         Arrays.sort(nums);

 6         //设置剩下两个数字的目标值

 7         int target = 0;

 8         //建立返回的list

 9         List<List<Integer>> result = new LinkedList<>();

10         //定义hashset

11         Set<Integer> hashset = new HashSet<>();

12         for(int i = 0;i < nums.length - 2 ; i++){

13             // 需要和上一次枚举的数不相同

14             if ( i > 0 && nums[ i ] == nums[ i - 1]) {

15                 continue;

16             }

17             target = 0 - nums[i];

18             //pre为上一个符合条件的num[j],定义为Integer.MAX_VALUE是为了避免与输入冲突

19             int pre = Integer.MAX_VALUE;

20             for(int j = i + 1; j < nums.length ; j++){

21                 //hashset中需要寻找的值

22                 int other = target - nums[j];

23                 if (hashset.contains(other)) {

24                     //判断当前的num[j]是否重复

25                     if(pre == nums[j]){

26                         continue;

27                     }

28                     result.add(new LinkedList<>(Arrays.asList(nums[i], other , nums[j] )));

29                     pre = nums[j];

30                 }

31                 //未找到对应的other值，就将当前nums[j]插入hashset

32                 hashset.add(nums[j]);

33             }

34             //清空hash表

35             hashset.clear();

36         }

37         return result;

38     }

39 }

复杂度分析：

时间复杂度：，其中N是数组中的元素数量。排序时间复杂度是，然后hashset是。
空间复杂度：。hashset中最多需要存n-2个数。

提交结果：

2. 三数之和（数组、hashset）的相关教程结束。