15. 三数之和

原题链接：

15. 三数之和

https://leetcode.cn/problems/3sum/description/

完成情况：

解题思路：

/**
 * 解题思路：
 *      首先给所有数排好序
 *      你返回所有和为 0 且不重复的三元组。，，，所有数字均不能重复
 *      固
 * @param nums
 * @return
 */
1
2
3
4
5
6
7
8

详细题解都在代码注释过程中

参考代码：

package LeetCode算法题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class __15三数之和 {
    /**
     * 解题思路：
     *      首先给所有数排好序
     *      你返回所有和为 0 且不重复的三元组。，，，所有数字均不能重复
     *      固
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int len = nums.length;
        if (nums == null || len < 3){
            return res;
        }
        Arrays.sort(nums);  //初始先将所有元素排好序，这样可以避免混乱的找要求数字
        for (int i=0;i<len;i++){        //从头到尾，逐个遍历，作为首个元素
            //然后后面的第二个，第三个采用双指针去进行选择
            //通过选择过程中的判断优化，实现时间复杂度的减少。
            if (nums[i]>0){     //如果当前数字大于0，则三数之和一定大于0，所以结束循环
                break;
            }
            if (i>0 && nums[i] == nums[i-1]){
                continue;   //去重
            }
            int Left = i+1,Right = len -1;
            while (Left < Right){
                int sum = nums[i] + nums[Left] + nums[Right];
                if (sum == 0){
                    res.add(Arrays.asList(nums[i],nums[Left],nums[Right]));     //满足条件则构造链表，把它加进去
                    //然后进行判断，左右指针都移动，并去除掉pass重复元素
                    while (Left < Right && nums[Left] == nums[Left+1]){
                        Left++;     //为下次遍历去重
                    }
                    while (Left < Right && nums[Right] == nums[Right-1]){
                        Right--;
                    }
                    Left++;
                    Right--;
                } else if (sum<0) { //左边小了
                    Left++;
                }else {     //右边大了
                    Right--;
                }
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

错误经验吸取