1 minute read

4/11

T18 四数之和

1、这道题是三数之和的直接应用版本，同样先对数组排序，套一层循环后重复三数之和解法即可。我一开始思路是降维成两两之和，想的太复杂，后续可以在题解区看看有无较好做法。

2、核心：数组长度题干说最多200个元素，这很关键。之前有一题是便于我们两两组合变成10的四次方，今天这题是便于我们套娃，也就是10的六次方一整个循环体。思路方向很重要，一个方向（拆成2+2）不好想要尽快考虑另一个方向（1+3），不要死磕。

3、注意边界问题，i、j小于n-3、n-2就是为后面几个数字考虑的

【4/10内容补充疑问】

a| b c d e….. f g，假如太小，左侧移动到C，假如还是太小，左侧移动到D，假如太大，右侧移动到F，假如太小，左侧继续右移。为何不考虑右侧为F、左侧为C的情况？】 已知：b到g递增（不单调）也就是 f<g b<c<d 已知：b+g < target c+g < target d+g > target d+f < target
是否可推出 c+f一定不等于target？

c+f<c+g<target 得证

所以，这个套路可以！

4/10

T15 三数之和【值得重做】

一、我的教训

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        3000x2999=6x100000(可接受)
        //先把所有的两数之和算出来（不去重），建立哈希表。键值为和，映射为一个四元元组（较小的数在前面，A，B。索引较小的在前面，C，D）。如出现重复键值，把新的四元元组链接在旧链表的后面。[无法应对极端情况，例如全都是1的nums，时间复杂度为n的三次方]
        //遍历nums的每个值，在哈希表中寻找相反数。假如存在，且C，D和当前值的索引都不同，取出所有映射的四元元组中的A，B，组成所有从小到达元素排列的三元元组，将元素拼接成字符串作为键值（用间隔符号例如——区分每个子数字）存进新哈希表里。若重复，无视。映射一律写为一。【去重方式非常低效，string 构造非常慢，hash string 也慢，内存占用大】（有无更好的写法？这件事本质是要高效得出所有互异的字符串元素）
        //输出新哈希表的所有键值
【逻辑复杂度极高，bug风险高，不优雅】
    }
};

PS：看到提示后想到的从零划分的延伸双指针法犯了不等价错误，漏掉了非相邻解和非单个负数元组等，等价思维等习惯要养好。

二、正确解法

排序+单循环套双指针
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());

        int n = nums.size();

        for (int i = 0; i < n; i++) {
            // 去重：第一个数
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    res.push_back({nums[i], nums[left], nums[right]});

                    // 去重：第二个数
                    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 -1 -1 … 2 的情况也不会漏解。因为叠叠乐-1 -1在第一个-1时已经被检测过，第二个-1作为i的循环时，后面的所有情况都在第一个-1时被探索过。因此可以跳过。后面的两个去重类似。

【关键问题】

当sum小于零时，左++。那么假如左++时突变很大的值，sum一下子大于零，按照代码逻辑该右减减。如何能保证这种走法可以将所有可能符合的解包含呢？我需要严格的数学证明或思维证明。

【解答（自己思考出来的哈哈）】

该问题等价于证明：对于所有可能的l，我们已经找到了所有可能的r。假如l从最小的可能值开始，那么r从最大值往左走直到走到对于该l正确的值。如果r一开始就太小，说明没有解了，l得增加。这和代码逻辑一致。如果正好，取出，加入解集，对于l、r分别去重，r再往左走的话由于变小了三者之和不可能为零，所以这一轮不动r了。l的这一轮就解决完毕（假设有解），再进行下一轮。核心：l既然已经增大，那么r之前走过的路由于更大，加上当前l对应的值以及循环时的i对应的值，这三者之和一定是正数（之前该和为零），因此这一段可以直接忽略。直到l大于r。假如一直到l超过r都无解，则这轮无解。

4/9

T1 两数之和

注意审题，不要看完题干后不细看样例就开始思考。题干一些文字你可能会误解，例如本题中【不能使用两次相同的元素】在例子中阐明了是不能一个下标用两次，而非不能一个数值用两次。

T454 两数相加二

1、转化条件时一定要关注是否全等，不多增也不漏掉情况。此题从四个数字和拆分成两组数之和时，不能用互异性处理，因为同样的值可能是不同下标组合导致的。同样，不能一一抵消，因为一个集合里的不同元素（同一值）都要用到另一个集合里同一个元素的相反数（如果存在多个元素同一值则也多次用到）。我一开始少算了情况。

2、留心10的次方对应2的次方的数量级，这一题没有超过int范围

3、保持节省空间的好习惯：num3、4不需要再开一个哈希表，也不必嵌套变成四次方。直接单独开一个两层循环，把相反数作为目标值寻找num1、2构造的map即可。核心：两个两层循环无论如何都是必要的，开新map不会减少这一点；总归有一个组是要担任遍历角色的，担任该角色无需有map；map真正优化的是将4次方变成2次方，有一组有映射值计数即可

4、不必使用字符串拼接下标等复杂方式做映射值，用value计算键值出现次数即可。核心：双重循环遍历时已确保下标组合互异性，后面又只用到了组合次数而无需具体下标。

总结：题干要求什么，就求什么。删去没必要的，确保必要的达标。

T383 赎金信

简单，略

4/8

本周开始一律使用C++编程

【T202 快乐数】

这一题我想复杂了，以为要有很巧妙的解决方式，看了题解才知道原来是我误会了时间复杂度。也就是逐位计算+等待循环可能没有我想的那么长，直接logn叠加循环即可，所以判断是否进入无限循环只需观察有无重复出现的sum，若无，等待sum值为一即可，这也是此题目前放在哈希类别和简单标签下的原因之一。

这道题给我的启示：看起来很诡异的没有妙解的题目，可能比我想象的简单。当然，如何证明无限循环次数有限至一个合理值，有待考虑。

You May Also Enjoy