leetCode:三数之和

题目：
给你一个整数数组 nums ，判断是否存在三元组 [nums, nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums + nums[j] + nums[k] == 0 。请你返回全部和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
解题思绪历程：

1. 第一个想到的方法三个循环，第一个循环从数组的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),但是如果使用双指针，这个算法会不会可以优化？
3. O(N^3)代码：
4. Arrays.sort(nums);
5.     System.out.println(Arrays.toString(nums));
6.     if (nums.length < 3) {
7.         return null;
8.     }
9.     int sum = 0;
10.     List<List<Integer>> lists = new ArrayList<>();
11.     List<Integer> inList = new ArrayList<>();
12.     if (nums.length == 3) {
13.         sum = nums[0] + nums[1] + nums[2];
14.         if (sum == 0) {
15.             inList.add(nums[0]);
16.             inList.add(nums[1]);
17.             inList.add(nums[2]);
18.             lists.add(inList);
19.         }
20.         return lists;
21.     }
22.     for (int i = 0; i < nums.length - 2; i++) {
23.         if (i > 0 && nums[i] == nums[i - 1]) {
24.             continue;
25.         }
26.         for (int right = i + 1; right < nums.length - 1; right++) {
27.             if(nums[right] == nums[right - 1] && right - i > 1){
28.                 continue;
29.             }
30.             int temp = right + 1;
31.             while(temp <= nums.length-1){
32.                 if(nums[temp] == nums[temp - 1] && temp - right > 1){
33.                     ++temp;
34.                     continue;
35.                 }
36.                 inList = new ArrayList<>() ;
37.                 if (nums[i] + nums[right] + nums[temp] == 0) {
38.                     inList.add(nums[i]);
39.                     inList.add(nums[right]);
40.                     inList.add(nums[temp]);
41.                     lists.add(inList);
42.                 }
43.                 temp++;
44.             }
45.         }
46.     }
47.     return lists;
48. }

复制代码

1. 第二种方法：维持前两个循环不变，在第二个循环上添加一个指针，并且得到目标值是-nums[i],这个指针从nums[]的末端开始前移，如果移动到跟第二个循环变量j相等，则直接跳出循环，指针前移的条件是m>j,nums[j] + nums[m] >
2. -nums[i],最后将nums[j] + nums[m] == -nums[i]的索引存入新的集合中，然后将该集合添加至要返回的集合中并返回，此时算法的时间复杂度是O(N^2)
3. O(N^2)代码：
4. public static List<List<Integer>> secondThreeSum(int[] nums) {
5.     nums = Arrays.stream(nums).sorted().toArray();
6.     Arrays.sort(nums);
7.     System.out.println(Arrays.toString(nums));
8.     if (nums.length < 3) {
9.         return null;
10.     }
11.     int sum = 0;
12.     List<List<Integer>> lists = new ArrayList<>();
13.     List<Integer> inList = new ArrayList<>();
14.     if (nums.length == 3) {
15.         sum = nums[0] + nums[1] + nums[2];
16.         if (sum == 0) {
17.             inList.add(nums[0]);
18.             inList.add(nums[1]);
19.             inList.add(nums[2]);
20.             lists.add(inList);
21.         }
22.         return lists;
23.     }
27.     for (int i = 0; i < nums.length - 2; i++) {
28.         if (i > 0 && nums[i] == nums[i - 1]) {
29.             continue;
30.         }
31.         int target = -nums[i];
32.         int temp = nums.length - 1;
33.         for (int right = i + 1; right < nums.length - 1; right++) {
35.             if(nums[right] == nums[right - 1] && right - i > 1){
36.                 continue;
37.             }
40.             while((nums[right] + nums[temp]) > target && temp > right) {
41.                 --temp;
42.             }
43.             if(temp == right){
44.                 break;
45.             }
46.             inList = new ArrayList<>() ;
47.             if (nums[right] + nums[temp] == target) {
48.                 inList.add(nums[i]);
49.                 inList.add(nums[right]);
50.                 inList.add(nums[temp]);
51.                 lists.add(inList);
52.             }
53.         }
54.     }
55.     return lists;
56. }

复制代码

1.  

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。