tips： unordered_map用来存储数组（val，index）可以快速找到目标值的索引。

1、454四数相加II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

我的思路： 一开始我想的类似动态规划的思路一样，把从下往上一层一层的计算求和和数量，用HashMap存储，最后直接find查找，这样复杂度有点大。
代码随想录： 他把上两行遍历求和统计在map中，下两行也遍历，遍历途中就直接find上两行的map里有没有合适的。而我是全部求出来。1两数之和也是类似思路。

  • 多层迭代分解成多个子问题，这样比全部一起迭代快，全部一起迭代是n^4，但是分解为上下两部分时2*n^2。
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
// 我的
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        std::unordered_map<int,int> mapi,mapj,mapk,mapl; //val idx
        for(int i = 0;i<nums1.size();i++){
            mapl[nums4[i]]++;
        }
        for(int i = 0;i<nums1.size();i++){
            for(auto &l:mapl){
                mapk[nums3[i]+l.first]+=l.second;
            }
        }
        for(int i = 0;i<nums1.size();i++){
            for(auto &k:mapk){
                mapj[nums2[i]+k.first]+=k.second;
            }
        }  
        for(int i = 0;i<nums1.size();i++){
            for(auto &ii:mapj){
                mapi[nums1[i]+ii.first]+=ii.second;
            }
        } 

        return mapi[0];   
    }
};
//代码随想录
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        std::unordered_map<int,int> map; //val idx
        for(int i = 0;i<nums1.size();i++)
        for(int j = 0;j<nums2.size();j++){
            map[nums1[i]+nums2[j]]++;
        }

        int len = 0;

        for(int i = 0;i<nums1.size();i++)
        for(int j = 0;j<nums2.size();j++){
            auto it = map.find(-nums3[i]-nums4[j]);
            if(it!=map.end()){
                len+=it->second;
            }
        }
        return len;
    }
};

2、383赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。

我的思路： ：这道题之前遇到过类似的242有效的字母异位词，按照我常规的思路就是直接两个数组都用Hashmap把元素和出现的次数存起来，然后两个map作比较看看他们的数量是否均等。但是在代码随想录-242有效的字母异位词学到了新思路，就是统计字符串1在map中，然后遍历字符串2，每遍历一次对应的map中的对应字符的数量-1，最后map中全为0则符合题意。
代码随想录： ：和我说的方法一样。与之不同的是，他用一个数组来代替HashMap，因为题目说字符都是小写英文，所以是有限的，用数组足够，注意看题。

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
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        std::unordered_map<char,int> ran,mag;
        int i = 0;
        while(i<ransomNote.size()){
            ran[ransomNote[i]]++;
            i++;
        }
        i=0;
        while(i<magazine.size()){
            if(ran[magazine[i]]!=0){
                ran[magazine[i]]--;
            }
            i++;
        }
        for(auto it:ran){
            if(it.second!=0)return false;
        }
        return true;
    }
};
// 代码随想录
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        //add
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        for (int i = 0; i < magazine.length(); i++) {
            // 通过record数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            // 如果小于零说明ransomNote里出现的字符，magazine没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};

3、15三数之和

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

常用Tips： 把数组先排序，再处理。

我的思路： 这道题耗费很长时间没做出来。这道题应该是1两数之和的加强版，首先都是在一个数组上寻找两个或多个值之和等于target的元素。我的思考是需要保证搜索时多个数的索引不能出现交叉，比如i=10，那就要一只在0~i之间，k就要在0~j之间。不然就会出现重复搜索，加慢速度。

  • 怎么保证搜索过三个元素值的不在重复？
    我的思考： 三个数不能出现重复的，比如{1,2,5}和{5,2,1}就重复了。问题是有没有什么机制找出他们的共性？？晕了一下我脑子里出现了一些操作，比如排序之后它两每个元素就都相同，不知道是什么时候刷题刷出这个感觉。但是如果用HashMap的话，这是三个元素没法放在键值里，必须自己重写Hash函数。于是由于我之前看Apollo的代码在写A*算法时用到了将下标转为字符串的做法，我也就萌生了这个想法。

我写的： 只通过了309/313个数据，其他的超时。可能是使用string做Hash键的原因。

代码随想录： 两层for循环就可以确定 两个数值，可以使用哈希法来确定 第三个数 0-(a+b) 或者 0 - (a + c) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。其他思路比较好的思路是先排序，再双指针搜索。

思考： 在1两数之和中用了一层for循环，第二个数用HashMap确定，这道题我一开始想其他的牛b方法，硬是想不到。最后我还是前两个数用for循环，最后一个数用HashMap。但是看了代码随想录之后有了些反思：很多时候解题并不需要什么NB的方法，只是我过分追求于完美导致了最后首尾难顾，时间也过去了。谨记：追求完美，面面俱到，很难成功！！

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
//我的
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<int,vector<int>> maps;
        std::unordered_set<string> res;
        vector<vector<int>> re;
        for(int i = 0;i< nums.size();i++){
            for(int j = 0;j<i;j++){
                auto it = maps.find(-nums[i]-nums[j]);
                if(it!=maps.end()){
                    for(auto &k:it->second){
                        if(k<j){
                            vector<int> temp({nums[i],nums[j],nums[k]});
                            sort(temp.begin(),temp.end());
                            auto str = to_string(temp[0])+"_"+to_string(temp[1])+"_"+to_string(temp[2]);
                            if(res.find(str)==res.end()){
                                re.emplace_back(vector<int>({nums[i],nums[j],nums[k]}));
                            }
                            res.emplace(str);
                        }
                    }
                }
            }
            maps[nums[i]].emplace_back(i);
        }
        return re;
    }
};

// 看了代码随想录的视频后我写的
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        std::sort(nums.begin(),nums.end());
        vector<vector<int>> res;

        int left = 1;
        int right = 1;
        
        for(int i = 0;i< nums.size()-2;i++){
            left = i+1;
            right = nums.size()-1;

            if(nums[i]>0)continue; //剪枝
            if(i!=0 && nums[i]==nums[i-1])continue;  //剪枝
            int target = -nums[i];

            while(left < right){
                if(left!=i+1 && nums[left]==nums[left-1]){
                    left++;
                    continue;
                }  //剪枝
                if(right!=nums.size()-1 && nums[right]==nums[right+1]){
                    right--;
                    continue;
                }  //剪枝

                if(nums[left]+nums[right]-target==0){
                    res.emplace_back(vector<int>({nums[i],nums[left],nums[right]}));
                    left++;
                    right--;
                }else if(nums[left]+nums[right]-target<0){
                    left++;
                }else if(nums[left]+nums[right]-target>0){
                    right--;
                }
            }
        }
        return res;
    }
};

// leetcode 代码随想录
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            // 错误去重a方法，将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            // 正确去重a方法
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};

4、18四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

我的思路： 这道题三数之和的进阶版。我的思路是前两个数嵌套for循环，后两个数用双指针。
遇到的几个坑，折腾了好久：

  • for(int i = 0;i< nums.size()-3;i++)这句代码中num.size()返回的是size_t(long unsigned int)无符号类型，所以-3之后如果是负数会转换为极大的正数。一直循环。。正确的做法for(int i = 0;i< (int)nums.size()-3;i++)。
  • if(nums[i]>target)continue; 剪枝只有在target=0时才有效。替换为nums[i] > target && (nums[i] >=0 || target >= 0)

代码随想录

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
// 我的代码
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        std::sort(nums.begin(),nums.end());
        vector<vector<int>> res;

        int left = 1;
        int right = 1;
        
        for(int i = 0;i< (int)nums.size()-3;i++){
            // if(nums[i]>target)continue; //剪枝
            if(i!=0 && nums[i]==nums[i-1])continue;  //剪枝

            for(int j = i+1;j< (int)nums.size()-2;j++){
                if(j!=i+1 && nums[j]==nums[j-1])continue;  //剪枝
                left = j+1;
                right = nums.size()-1;
                long target1 = (long)target-nums[i]-nums[j];
                while(left < right){
                    if(left!=j+1 && nums[left]==nums[left-1]){
                        left++;
                        continue;
                    }  //剪枝
                    if(right!=nums.size()-1 && nums[right]==nums[right+1]){
                        right--;
                        continue;
                    }  //剪枝

                    if(nums[left]+nums[right]==target1){
                        res.emplace_back(vector<int>({nums[i],nums[j],nums[left],nums[right]}));
                        left++;
                        right--;
                    }else if((long)nums[left]+nums[right]-target1<0){
                        left++;
                    }else if((long)nums[left]+nums[right]-target1>0){
                        right--;
                    }
                }

            }

        }
        return res;
    }
};