第15题. 三数之和

力扣题目链接

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

这题。。。放弃了，看题解吧。九成五的测例通过，说明思路是正确的，只是超时。没办法，测例太长了。

package com.programmercarl.hashtable;

import java.util.*;

/**
 * @ClassName sum3
 * @Descriotion TODO
 * @Author nitaotao
 * @Date 2022/6/21 15:03
 * @Version 1.0
 **/
public class sum3 {
  
    public static List<List<Integer>> threeSum(int[] nums) {
        /**
         * 依旧可以使用hashmap，
         * 三数之和，其实当前两个数确定时，最后一个数已经确定了。
         * 可以把前两数获取到，再计算最后一个数，为防止一样，三数排序作为键
         */
        List<List<Integer>> result = new ArrayList<>();
        int temp;
        HashMap<String, String> map = new HashMap<>();
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                //第三个数
//                temp = 0 - nums[i] - nums[j];
                temp = -(nums[i] + nums[j]);
                //三数排序,降序
                String key = order3(nums[i], nums[j], temp);
                map.put(key, i + "#" + j + "=" + temp);
            }
        }
        //只有出现过的才算正确
        Set<String> set = new HashSet<>();
        Set<String> keys = map.keySet();
        for (String key : keys) {
            for (int i = 0; i < nums.length; i++) {
                //值
                String valStr = map.get(key);
                //当前被比较的值，不一定存在
                int value = Integer.parseInt(valStr.split("=")[1]);
                if (value == nums[i]) {
                    //再判断这个数是不是自己
                    //如果不是，再添加
                    //位置进行比较
                    //位置
                    String[] pos = valStr.split("=")[0].split("#");
                    if (!(pos[0].equals(String.valueOf(i)) || pos[1].equals(String.valueOf(i)))) {
                        set.add(key);
                    }
                }
            }
        }
        //处理结果集,去重
        for (String res : set) {
            List<Integer> resultList = new ArrayList<>();
            String[] split = res.split("#");
            resultList.add(Integer.valueOf(split[0]));
            resultList.add(Integer.valueOf(split[1]));
            resultList.add(Integer.valueOf(split[2]));
            result.add(resultList);
        }
        return result;
    }

    /**
     * 三数降序排序
     *
     * @param nums1
     * @param nums2
     * @param nums3
     * @return
     */
    public static String order3(int nums1, int nums2, int nums3) {
        if (nums1 > nums2) {
            if (nums1 > nums3) {
                //nums1最大
                if (nums2 > nums3) {
                    return "" + nums1 + "#" + nums2 + "#" + nums3;
                } else {
                    return "" + nums1 + "#" + nums3 + "#" + nums2;
                }
            } else {
                //nums1没nums3大
                return "" + nums3 + "#" + nums1 + "#" + nums2;
            }
        } else {
            //nums2>nums1
            if (nums2 > nums3) {
                if (nums1 > nums3) {
                    return "" + nums2 + "#" + nums1 + "#" + nums3;
                } else {
                    return "" + nums2 + "#" + nums3 + "#" + nums1;
                }
            } else {
                //nums1最大
                return "" + nums3 + "#" + nums2 + "#" + nums1;
            }
        }
    }
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

我的思路是用hashmap做
三数之和，其实当前两个数确定时，最后一个数已经确定了。
可以把前两数获取到，再计算最后一个数，为防止一样，三数排序作为键
为了防止键重复，先把元素排序，再存在键中，值的构成是 第一个元素的位置#第二个元素的位置=需要的元素的值。
符号只是标记为。
因为两个值确定了，第三个值就已经确定了，先不管有没有，先存起来。
再遍历一遍，看看第三个值在不在，如果存在，且位置不是前两个元素的值，则成功找到这个序列。

==============================================================================
hhhhh
在看题解，就差念我身份证号了。

真就一个力扣搞一天了。
1：如果数组长度<3直接返回。
2：数组排序，升序。
3：从第一位开始为基准，建立右边第一个元素为左指针，最后一个元素为右指针。
4：如果第一个元素>0，即最小的元素>0，直接返回吧，不用看了。
5：如果除了第一个元素，之后的基准元素和前一个一样，则跳过，因为结果重复了。
6：以基准元素为第一个和数，之后的第二个和第三个和数，分别来自左指针和右指针。
7：左右指针变换规律和基准元素相似，和自己的上个元素不得重复，不然就结果重复了。
8：直到左、右都和自己的上一个不同时，根据sum的值进位，值>0，则右边减一点，值<0，则左边加一点，毕竟是升序的。直到左右重合，结束循环。
9：基准元素不断后移。

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        //数组的长度
        int len = nums.length;
        //当数组的长度小于3时，直接退出
        if (len < 3) {
            return result;
        }
        //将数组排序，升序
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            //如果遍历的起始元素大于0，则直接退出
            //因为是升序的，说明最小值都大于0，直接结束
            if (nums[i] > 0) {
                break;
            }
            //去重，当起始的值等于前一个元素，那么得到的结果将会与前一次相同。
            /**
             * 诸如 -1 -1 2
             * 只用计算第一个-1的，会把第二个-1计入
             * 再以第二个-1计算时，在多代入第一个就重复了。
             */
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //左指针
            int left = i + 1;
            //右指针
            int right = len - 1;
            //当左不等于右时
            while (left < right) {
                //三数相加
                int sum = nums[i] + nums[left] + nums[right];
                //如果等于0，则加入结果集
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //将左右指针移动时，先对左右指针的值进行判断，重复则跳过
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    //去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    //当左边和右边都不在和前一个相同时
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                }
            }
        }
        return result;
    }
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