说好的周更两篇，人的惰性真是可怕，周末瘫床上就什么都不想动了，挣扎着还是坚持上来更新一篇吧，虽然没人看。

Problem 1.Two Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

这里贴一下中文版的翻译，为什么这里要用英文的题目？一方面顺便锻炼下英语阅读，另一方面上次面某公司的时候面试官也是给的英语题目，虽然会用普通话给你翻译一遍。

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

思路

先来分析下题目，题目中的意思是找出所有满足a+b+c=0条件的解，刚拿到感觉跟leetcode - 1.Two Sum两数求和有点像，不过这里返回值不是原始数组的下标，而是满足条件的值，但是总体思路上基本一样。暴力搜索这里就不提了，个人思考了好一会，觉得这题再怎么判断和优化都逃不掉双重循环的判断，因为必须确定其中的两个数才能判断第三个数是否存在，因此上来就排序对总体的时间复杂度影响不算大（最好情况时间复杂度在O(nlogn)，最坏的情况也是O(n^2)），排序的目的是什么？我们来看题目，返回的三元组中不允许重复，排序过后我们的内外层循环能跳过那些相同的元素。最外层扫描数组是在所难免的，而内层我们采用Two Sum的思路，但是其中需要借助一个hashSet去重，确定了整体思路，我们来实现一波。

双重循环借助hashSet去重搜索

    /**
     * 双重循环借助hashSet去重搜索
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums , 0 , nums.length);
        List<List<Integer>> result  = new ArrayList<>();
        for(int i = 0; i < nums.length - 1 ; i ++){
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            HashSet<Integer> set = new HashSet<>();
            for(int j = i + 1; j < nums.length ; j++){
                //这里必须 nums[j-2] = nums[j-1] = nums[j]才跳过本次循环，不然会排除掉{0,0,0}的情况
                //其实也可以单独将{0,0,0}情况独立判断，这里只是简单的去掉连续3个数重复的情况，hashSet才能最终保障结果集不重复
                if(j > i + 2 && nums[j] == nums[j - 1] && nums[j - 2] == nums[j - 1]){
                    continue;
                }
                //求出第三个数的值
                int k = -(nums[i] + nums[j]);
                //这里要移除掉第三个数的值，防止后面的重复扫描
                if(set.remove(k)){
                    result.add(Arrays.asList(nums[i] , nums[j] , k));
                    //
                }else{
                    set.add(nums[j]);
                }
            }
        }
        return result;
    }

时间复杂度：大约O(n^2)
空间复杂度：O(n)
leetcode上运行耗时大概在300 ms左右

问题
1. 时间复杂度不稳定，依赖于hashSet的hash函数，冲突较多最坏情况时间复杂度可能退化到O(n^3)

这里想了好一会发现没什么能优化的，实在没什么思路。于是看了下leetcode的官方解答，下面标上了注释，方便看懂代码。

借助数组值映射到新数组下标上，新数组值表示元素出现次数

     /**
     * 三数求和leetcode标准范例
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3)
            return Collections.emptyList();
        //以下代码目的在于以一个循环中统计出数组中的最大，最小值，以及等于0，小于0，大于0的数字个数
        List<List<Integer>> res = new ArrayList<>();
        int minValue = Integer.MAX_VALUE;
        int maxValue = Integer.MIN_VALUE;
        int negSize = 0;
        int posSize = 0;
        int zeroSize = 0;
        for (int v : nums) {
            if (v < minValue)
                minValue = v;
            if (v > maxValue)
                maxValue = v;
            if (v > 0)
                posSize++;
            else if (v < 0)
                negSize++;
            else
                zeroSize++;
        }
        //对于存在3个0的特殊情况，加入结果集
        if (zeroSize >= 3)
            res.add(Arrays.asList(0, 0, 0));
        //只有大于0或者小于0的数，直接返回
        if (negSize == 0 || posSize == 0)
            return res;
        //这段判断目的在于收缩最大最小值的范围，这里的minValue和maxValue是后面扫描的最大最小值，并不是数组的最大最小值
        if (minValue * 2 + maxValue > 0)
            maxValue = -minValue * 2;
        else if (maxValue * 2 + minValue < 0)
            minValue = -maxValue * 2;

        /**
         * 以一层循环扫描上面得到的收缩集的返回，将值映射到数组的下标上，将出现次数映射到map数组的值上
         * 注意：这里以最小值为map数组的基础偏移量0，所以判断值是否存在以map[v - minValue]==0为判断根据，该map数组中的值就是元素在原始数组中出现的次数
         * 得到收缩后去重的正数集，和负数集
         */
        int[] map = new int[maxValue - minValue + 1];
        int[] negs = new int[negSize];
        int[] poses = new int[posSize];
        negSize = 0;
        posSize = 0;
        for (int v : nums) {
            if (v >= minValue && v <= maxValue) {
                if (map[v - minValue]++ == 0) {
                    if (v > 0)
                        poses[posSize++] = v;
                    else if (v < 0)
                        negs[negSize++] = v;
                }
            }
        }
        //将得到的正数集和负数集排序，这里用的是快排
        Arrays.sort(poses, 0, posSize);
        Arrays.sort(negs, 0, negSize);
        /**
         * 这里以负数集为循环外层，以map数组为判断元素是否存在的根据，加入结果集中
         */
        int basej = 0;
        for (int i = negSize - 1; i >= 0; i--) {
            int nv = negs[i];
            //第一个数为负数，则余下两个数必定存在一个正数，并且该正数一定大于或等于该负数的一半，令这个数为minp
            int minp = (-nv) >>> 1;
            //找到数组中存在的大于等于minp的最小的扫描正数集的下标令其为basej
            while (basej < posSize && poses[basej] < minp)
                basej++;
            //从basej开始扫描正数集
            for (int j = basej; j < posSize; j++) {
                int pv = poses[j];
                //定位到第三个数
                int cv = 0 - nv - pv;
                //若第三个数在nv和pv之间
                if (cv >= nv && cv <= pv) {
                    //cv等于nv，说明三个数中两个负数相等，判断nv在map数组上数量是否大于1,也就是原始数组中是否存在两个负数nv
                    if (cv == nv) {
                        if (map[nv - minValue] > 1)
                            res.add(Arrays.asList(nv, nv, pv));
                    //cv等于pv，说明三个数中两个正数相等，判断pv在map数组上数量是否大于1,也就是原始数组中是否存在两个正数pv
                    } else if (cv == pv) {
                        if (map[pv - minValue] > 1)
                            res.add(Arrays.asList(nv, pv, pv));
                    //否则看第三个数在map数组上是否大于0，大于表示存在，加入结果集
                    } else {
                        if (map[cv - minValue] > 0)
                            res.add(Arrays.asList(nv, cv, pv));
                    }
                //若第三个数比第一个数自身还小，终止本次循环，因为不允许出现重复集合，所以第三个数只能在nv和pv之间
                } else if (cv < nv)
                    break;
            }
        }
        return res;
    }

时间复杂度：大约O(n^2)
空间复杂度：O(n)
leetcode上运行耗时大概在27 ms左右

问题
1.算法依赖于数组中数据的值的大小，在数组中数量较小而最大最小值绝对值比较大的情况下大量空间被浪费
2.算法实现步骤比较繁琐

其实这里大概分为三部分，这里代码比较长，我们一部分一部分来拆解。

第一部分（列举特殊情况，收缩扫描范围）

        //以下代码目的在于以一个循环中统计出数组中的最大，最小值，以及等于0，小于0，大于0的数字个数
        List<List<Integer>> res = new ArrayList<>();
        int minValue = Integer.MAX_VALUE;
        int maxValue = Integer.MIN_VALUE;
        int negSize = 0;
        int posSize = 0;
        int zeroSize = 0;
        for (int v : nums) {
            if (v < minValue)
                minValue = v;
            if (v > maxValue)
                maxValue = v;
            if (v > 0)
                posSize++;
            else if (v < 0)
                negSize++;
            else
                zeroSize++;
        }
        //对于存在3个0的特殊情况，加入结果集
        if (zeroSize >= 3)
            res.add(Arrays.asList(0, 0, 0));
        //只有大于0或者小于0的数，直接返回
        if (negSize == 0 || posSize == 0)
            return res;
        //这段判断目的在于收缩最大最小值的范围，这里的minValue和maxValue是后面扫描的最大最小值，并不是数组的最大最小值
        if (minValue * 2 + maxValue > 0)
            maxValue = -minValue * 2;
        else if (maxValue * 2 + minValue < 0)
            minValue = -maxValue * 2;

第一部分比较好懂，其实就是统计最大最小值，正数，负数，0出现的次数，并且确定最后扫描的区间范围。首先列举下特殊情况，3个0的情况加入结果集，当只有正数或者负数的时候直接返回结果集，然后收缩后面扫描的范围。这里要注意，确定最大最小区间其实是依赖于数组的最大最小值，当最大值比最小值的两倍的负数还大，说明三个数中即使有两个最小值也不能满足a+b+c=0条件，最大值过大，扫描根本不需要扫描最大值这个值，收缩最大值到2倍最小值。最小值同理，这里就是各种判断条件收缩最后的扫描区间，降低时间复杂度。

第二部分（分离正数，负数，数据出现次数集合）

我们思考一下上面为什么要统计正数，负数的值？这是为了下面分离正数集（poses[]），和负数集（negs[]），为什么需要分离正数集合（poses[]）和负数集合（negs[]）？我们再来分析一下题目，找到 a+b+c=0满足条件的组合，除了0，0，0的情况三个数中必定存在一个正数，一个负数。所以最后列举组合的时候，我们可以从负数集（negs[]）出发作为外层循环的条件，但最后一个数我们不确定是正数还是负数，又因为题目需要排除掉重复的三元组，我们需要一个既能去重，又能承载内层循环的时候通过目标值寻找目标元素的数据结构。这时候其实我们的选择很多，既可以是hashmap,也可以是题目中的数组（map[]），以原始数组的值映射到新数组（map[]）的长度上，原始数组元素出现的次数为新数组（map[]）的值。显然，新数组（map[]）必须按照值得大小递增或递减顺序来组织数据结构。解答部分选用了数组的解决方案，其实这种方案也有弊端，就是在数组元素之间的差值较大，数量较少，而且最大最小值比较大的时候，这个数组的长度就会很大，很浪费空间。第二部分得最后对得到的正数集（poses[]）和负数集（negs[]）按大小排序。

         /**
         * 以一层循环扫描上面得到的收缩集的返回，将值映射到数组的下标上，将出现次数映射到map数组的值上
         * 注意：这里以最小值为map数组的基础偏移量0，所以判断值是否存在以map[v - minValue]==0为判断根据，该map数组中的值就是元素在原始数组中出现的次数
         * 得到收缩后去重的正数集，和负数集
         */
        int[] map = new int[maxValue - minValue + 1];
        int[] negs = new int[negSize];
        int[] poses = new int[posSize];
        negSize = 0;
        posSize = 0;
        for (int v : nums) {
            if (v >= minValue && v <= maxValue) {
                if (map[v - minValue]++ == 0) {
                    if (v > 0)
                        poses[posSize++] = v;
                    else if (v < 0)
                        negs[negSize++] = v;
                }
            }
        }
        //将得到的正数集和负数集排序，这里用的是快排
        Arrays.sort(poses, 0, posSize);
        Arrays.sort(negs, 0, negSize);

第三部分（双重循环得到结果集合）

经过上面一系列的操作，终于到了最后扫描得到结果的时候。我们得思考一下为什么上面需要对正数集（poses[]）和负数集（negs[]）排序？在第一种解法那里，排序是为了过滤那种其中一个满足情况的值出现连续3个相同数值的情况（例如：a + b + c = 0 ,其中a的值出现了3次），显然这里并不是为了去重，因为去重已经由数据出现次数集合(map[])来实现。其实这里仍然是为了最后扫描的时候，减少扫描的范围和次数。我们来看代码。

         /**
         * 这里以负数集为循环外层，以map数组为判断元素是否存在的根据，加入结果集中
         */
        int basej = 0;
        for (int i = negSize - 1; i >= 0; i--) {
            int nv = negs[i];
            //第一个数为负数，则余下两个数必定存在一个正数，并且该正数一定大于或等于该负数的一半，令这个数为minp
            int minp = (-nv) >>> 1;
            //找到数组中存在的大于等于minp的最小的扫描正数集的下标令其为basej
            while (basej < posSize && poses[basej] < minp)
                basej++;
            //从basej开始扫描正数集
            for (int j = basej; j < posSize; j++) {
                int pv = poses[j];
                //定位到第三个数
                int cv = 0 - nv - pv;
                //若第三个数在nv和pv之间
                if (cv >= nv && cv <= pv) {
                    //cv等于nv，说明三个数中两个负数相等，判断nv在map数组上数量是否大于1,也就是原始数组中是否存在两个负数nv
                    if (cv == nv) {
                        if (map[nv - minValue] > 1)
                            res.add(Arrays.asList(nv, nv, pv));
                    //cv等于pv，说明三个数中两个正数相等，判断pv在map数组上数量是否大于1,也就是原始数组中是否存在两个正数pv
                    } else if (cv == pv) {
                        if (map[pv - minValue] > 1)
                            res.add(Arrays.asList(nv, pv, pv));
                    //否则看第三个数在map数组上是否大于0，大于表示存在，加入结果集
                    } else {
                        if (map[cv - minValue] > 0)
                            res.add(Arrays.asList(nv, cv, pv));
                    }
                //若第三个数比第一个数自身还小，终止本次循环，因为不允许出现重复集合，所以第三个数只能在nv和pv之间
                } else if (cv < nv)
                    break;
            }
        }
        return res;

最外层是扫描负数集合没什么好说，我们看到int minp = (-nv) >>> 1;这句，这一句和while (basej < posSize && poses[basej] < minp) basej++;组合确定在正数集合中扫描开始的下标，这里之前对正数集排序的优势就显示出来了，我不需要扫描整个正数集就能找到大于basej位置元素的所有正数。我们对这些正数进行内层循环的遍历，遍历过程中判断第三个数在数据出现次数集合（map[]）中是否存在，存在就加入结果集合。因为正数集（poses[]）和负数集（negs[]）进行过排序，这样内外层循环扫描的正数和负数数值都是不重复的，因此就实现了去重的目的。

总结

观察leetcode标准解答发现，三数和求满足得解也逃避不了双重循环，归根究底还是因为三数中必须确定两个数才能确定第三个数，所以双重循环是无法避免的。至于第二种解法和第一种解法的时间差别，可以看到第二种解答采用了各种措施来缩小最终扫描检索的范围，所以最终表现出来对于leetcode上的测试用例耗时只有仅仅的27ms，但是这并不说明该算法就适用于任何情况，该算法还是有其弊端的，没有放之四海而皆准的解答。总的来说，第二种需要思考的时间可能更长一点，毕竟需要考虑排除各种情况。

后记

之前雄心壮志地想保持周更两篇，才发现写博客真的很费时间，虽然并没有考虑到语言如何组织之类的问题，但是随便一写一晚上就过去了，希望之后能坚持吧。这几天买的数据结构和算法导论马上到货了，是时候开搞了，打算边读书复习边弄脑图，省得面试弄出排序算法时间复杂度还答错的尴尬局面。2018年就剩最后一个月了，回想年初的目标，一半都没实现。不管怎样，学习和寻找自我是人终其一生的事业，与诸君共勉。