leetCode:三数之和

题目：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解题思路历程：

第一个想到的方法三个循环，第一个循环从数组的0索引（i）位置开始，第二个循环从数组的j(i+1)索引位置开始，第三个循环从数组的m（i+1+1）位置开始，然后输出nums[i]+nums[j]+nums[m] == 0的结果，但是这种做法会出现重复的三元组元素。如果需要去除这些重复元素，则需要再一次便历，这样算法的效率会大大降低，所以果断去除这种方式。所以在这种方式之后，我想如果把原始数组先排序，然后将排序之后的数组进行三重循环，每一层循环加一个if判断条件，如果当前位置元素与上一个位置元素的值相等，第一层循环的时候需要i>.0,第二重循环需要j-i>1,第三重循环需要m-j>1,这样输出的元素数组就不会再重复，此时算法的时间复杂度是O(N^3),但是如果使用双指针，这个算法会不会可以优化？
O(N^3)代码：
Arrays.sort(nums);
 System.out.println(Arrays.toString(nums));
 if (nums.length < 3) {
 return null;
 }
 int sum = 0;
 List<List<Integer>> lists = new ArrayList<>();
 List<Integer> inList = new ArrayList<>();
 if (nums.length == 3) {
 sum = nums[0] + nums[1] + nums[2];
 if (sum == 0) {
 inList.add(nums[0]);
 inList.add(nums[1]);
 inList.add(nums[2]);
 lists.add(inList);
 }
 return lists;
 }
 for (int i = 0; i < nums.length - 2; i++) {
 if (i > 0 && nums[i] == nums[i - 1]) {
 continue;
 }
 for (int right = i + 1; right < nums.length - 1; right++) {
 if(nums[right] == nums[right - 1] && right - i > 1){
 continue;
 }
 int temp = right + 1;
 while(temp <= nums.length-1){
 if(nums[temp] == nums[temp - 1] && temp - right > 1){
 ++temp;
 continue;
 }
 inList = new ArrayList<>() ;
 if (nums[i] + nums[right] + nums[temp] == 0) {
 inList.add(nums[i]);
 inList.add(nums[right]);
 inList.add(nums[temp]);
 lists.add(inList);
 }
 temp++;
 }
 }
 }
 return lists;
}

第二种方法：维持前两个循环不变，在第二个循环上添加一个指针，并且得到目标值是-nums[i],这个指针从nums[]的末端开始前移，如果移动到跟第二个循环变量j相等，则直接跳出循环，指针前移的条件是m>j,nums[j] + nums[m] >
-nums[i],最后将nums[j] + nums[m] == -nums[i]的索引存入新的集合中，然后将该集合添加至要返回的集合中并返回，此时算法的时间复杂度是O(N^2)
O(N^2)代码：
public static List<List<Integer>> secondThreeSum(int[] nums) {
 nums = Arrays.stream(nums).sorted().toArray();
 Arrays.sort(nums);
 System.out.println(Arrays.toString(nums));
 if (nums.length < 3) {
 return null;
 }
 int sum = 0;
 List<List<Integer>> lists = new ArrayList<>();
 List<Integer> inList = new ArrayList<>();
 if (nums.length == 3) {
 sum = nums[0] + nums[1] + nums[2];
 if (sum == 0) {
 inList.add(nums[0]);
 inList.add(nums[1]);
 inList.add(nums[2]);
 lists.add(inList);
 }
 return lists;
 }
 
 for (int i = 0; i < nums.length - 2; i++) {
 if (i > 0 && nums[i] == nums[i - 1]) {
 continue;
 }
 int target = -nums[i];
 int temp = nums.length - 1;
 for (int right = i + 1; right < nums.length - 1; right++) {
 if(nums[right] == nums[right - 1] && right - i > 1){
 continue;
 }
 while((nums[right] + nums[temp]) > target && temp > right) {
 --temp;
 }
 if(temp == right){
 break;
 }
 inList = new ArrayList<>() ;
 if (nums[right] + nums[temp] == target) {
 inList.add(nums[i]);
 inList.add(nums[right]);
 inList.add(nums[temp]);
 lists.add(inList);
 }
 }
 }
 return lists;
}