LeetCode_15 三数之和 （数组题）
题目地址：https://leetcode-cn.com/problems/3sum/
题目：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
试题分析：
这道题因为不允许使用暴力3层循环，所以如果没做过的话还是有一定难度的，对编码细节要求比较高，不小心就会出错。这道题和之前做过的两数之和其实思路上类似，也可以采用hashmap来实现， 可以在外层进行一次循环，再在内部循环两数之和等于target－当前外部循环的数值，但是这样会增加n个hashmap(n-1)的空间复杂度，这种解法的核心思路和两数之和查找思路一样，这个方案的时间复杂度为O(n2),空间复杂度为O(n2)。
下面我再介绍一种时间复杂度为O(n^2),但是空间复杂度为O(1)的算法。该算法不是依赖hashmap，而是巧妙的利用了有序数组的夹闭查找算法，因为在有序的数组中可以通过单次顺序查找避免走回头路，通过夹闭查找从两头并行向中间查找，当子循环中的夹闭查找的两个指针相遇则一次子循环结束。
该算法在实现过程中有几个注意点：
1）在循环过程中需要进行重复数的跳过操作；
2）在循环体内需要分3种情况分别进行考虑，a.当前循环三数相加小于目标值，因为内循环数组是从小到大有序的，所以这说明内循环的前值小值加上后值大值是不符合要求的，后值不能后退，那就需要前值继续＋1后移，取顺序更大的值；b.当前循环3数相加大于目标值，同理说明后值大值太大了，后值需要前移来取小值才有可能三数相加等于目标值；c.当前循环3数相加等于目标值，同理则表示三数复合要求，则将这3个数创建一个新的List并加到结果集中；
3）在内循环上面3种情况下，还要考虑有连续相等的数值的情况，那就需要在内循环的分支里分别根据3种情况进行下标的前后移动，这样可以减少内循环的次数，加速值查找。
代码：
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> resultList = new ArrayList<List<Integer>>();
if(nums.length<3){
return resultList;
}
int target = 0;
//先对数据进行从小到大排序，再进行夹击查找
Arrays.sort(nums);
int j,k;
for(int i=0;i<nums.length-2;i++){
j = i + 1;
//跳过重复的数
if(i>0 && nums[i]==nums[i-1]){
continue;
}
k = nums.length-1;
while(j<k){
if(nums[i]+nums[j]+nums[k]<target){
j++;//j右移动,取右边大数值
while(nums[j]==nums[j-1] && j<k){
j++;
}
}else if(nums[i]+nums[j]+nums[k]>target){
k--;
while(nums[k]==nums[k+1] && j<k){
k--;
}
}else{
List<Integer> result = new ArrayList<Integer>(3);
result.add(nums[i]);
result.add(nums[j]);
result.add(nums[k]);
resultList.add(result);
j++;
k--;
while(nums[j]==nums[j-1] && nums[k]==nums[k+1] && j<k){
j++;
}
}
}
}
return resultList;
}
源码路径：com.monkey01.array.ThreeSum_15
配套测试代码路径：test目录com.monkey01.array.ThreeSum_15Test
