leetcode 15.三数之和
第十五题：三数之和
1.排序 + 双指针：
和两数之和不同，但可以转化为类似的思路，即确定一个数，去找数组中是否有另外两个数之和等于它的相反数。本题的难点在于如何去除重复解，如果是无序数组，则需要对每个值所在的位置进行记录并进行比较。但如果是有序数组且相加结果为0，那么对于当第一个指针指向的位置大于0后，后序位置相加不可能为0，降低了复杂度。还要注意的是，遍历中会遇到值相同的元素，由于本题只要结果，遇到这样的元素应该跳过。
算法流程：
1.特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 null。
2.对数组进行排序。
3.遍历排序后数组： 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针 L=i+1，右指针 R=n−1，当 L<R时，执行循环：
当nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
若和大于 0，说明 nums[R] 太大，R 左移
若和小于 000，说明 nums[L] 太小，L 右移
复杂度分析：
时间复杂度：O(n^2)
空间复杂度：O(1)
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 3) return null;
Arrays.sort(nums);
int n = nums.length;
for (int i =0;i<n;i++){
if (nums[i] > 0) return result;
if (i>0 && nums[i] == nums[i-1]) {
continue;
}
int left = i+1;
int right = n-1;
while (left<right){
if (nums[i] + nums[left] + nums[right] == 0){
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
while (left < right && nums[left] == nums[left+1]) left+=1;
while (left < right && nums[right] == nums[right - 1]) right-=1;
left+=1;
right-=1;
}
else if (nums[i] + nums[left] + nums[right] > 0) {
right-=1;
}
else left+=1;
}
}
return result;
}