● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ● 18. 四数之和 ● 总结

四数相加II

将四层for循环暴力优化成2次2层遍历，第一次2层遍历将a+b的值存入map（重复则次数+1），第二次二层遍历将-（c+d）的值进行查找，如果匹配，则cnt += map存的次数值，注意是n次数不是+1，对应n种组合方式。

C++

C+往map里插入元素不用先Insert，直接访问索引+就好。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> res;
        for(int a : nums1) {
            for(int b : nums2) {
                res[a + b]++;
            }
        }
        
        int cnt = 0;
        for(int c : nums3) {
            for(int d : nums4) {
                if(res.find(-(c + d)) != res.end()) {
                    cnt += res[-(c + d)];
                }
            }
        }
        return cnt;
    }
};

C#

添加Dic新纪录的时候记得判断一下存不存在，C+可以不判断，C#需要。

public class Solution {
    public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Dictionary<int, int> dic = new Dictionary<int, int>();
        foreach(int a in nums1) {
            foreach(int b in nums2) {
                if(dic.ContainsKey(a + b)) {
                    dic[a + b] ++;
                } else {
                    dic.Add(a + b, 1);
                }
            }
        }
        int cnt = 0;
        foreach(int c in nums3) {
            foreach(int d in nums4) {
                if(dic.ContainsKey(-(c + d))) {
                    cnt += dic[-(c + d)];
                }
            }
        }
        return cnt;
    }
}

赎金信

和昨天有效字母的异位词差不多，有点不同在于只要遍历待匹配string出现单词不用就return false。

字母就26个匹配值，数组更优。

alt

C++

数组。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int res[26] = {0};
        for(int i  = 0; i < magazine.size(); i++) {
            res[magazine[i] - 'a']++;
        }
        for(int i = 0; i < ransomNote.size(); i++) {
            if(res[ransomNote[i] - 'a'] == 0) {
                return false;
            } else {
                res[ransomNote[i] - 'a']--;
            }
        }
        return true;
    }
};

C#

Dic。

public class Solution {
    public IList<IList<int>> ThreeSum(int[] nums) {
        List<IList<int>> res = new List<IList<int>>();
        Array.Sort(nums);
        for (int i = 0; i< nums.Length - 2; i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.Length - 1;
            while(right > left) {
                if(nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else if(nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else {
                    res.Add(new List<int>{nums[i], nums[left], nums[right]});
                    while(left < right && nums[left] == nums[left + 1]) left++;
                    while(left < right && nums[right] == nums[right - 1] ) right--;
                    right--;
                    left++;
                }
            }
        }
        return res;
    }
}

public class Solution {
    public bool CanConstruct(string ransomNote, string magazine) {
        Dictionary<int, int> dic = new Dictionary<int, int>();
        for(int i = 0; i < magazine.Length; i++) {
            if(dic.ContainsKey(magazine[i] - 'a')) {
                dic[magazine[i] - 'a']++;
            } else {
                dic.Add(magazine[i] - 'a', 1);    
            }
        }
        for(int i = 0; i < ransomNote.Length; i++) {
            if(!dic.ContainsKey(ransomNote[i] - 'a')) {
                return false;
            } else {
                if(dic[ransomNote[i] - 'a'] == 0) return false;
                dic[ransomNote[i] - 'a']--;
            }
        }
        return true;
    }
}

三数之和

掌握不是很好，二刷注意。

遍历指针i去重是向前(上次遍历的方向)去。
left,right找到结果后在去重，不要提前去重，会漏掉-1,-1,2这种情况。
双指针要求数组是排序的，所以二数之和不能用双指针，哈希法去重很麻烦不适用这题。
注意下如果循环条件剪了- 2， -1，C++里nums.size()是无符号整型，如果nums.size()小于2， nums.size()- 2变成了负数，就会进入循环，然后越界，要单独if(nums.size() < 4) return res;C#就不用。

C++

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] > 0) return result;
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.size() - 1;
            while(right > 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]});
                    while(right > left && nums[right] == nums[right - 1]) right--;
                    while(right >left && nums[left] == nums[left + 1]) left++;
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};

四数之和

在三数的基础上再套一层循环，注意剪枝由>0变成>target&& n1>= 0，尤其是后面限定正数是很重要的，因为如果下一个数如果是负数，和反而可能变小接近target,要限定当前和>=0,由于排序后面的数肯定也>=0,=0是可以的，因为即使四个数都是0相加等于0，target <0也不符合，剪掉即可。

两层循环分两次剪枝。
双指针法一定要先对数组排序。
四数相加可能会溢出，注意long处理一下。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 1; i++) {
            int n1 = nums[i];
            if (n1 > target && n1 >= 0) {
                break;
            }
            if (i > 0 && n1 == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.size(); j++) {
                int n2 = nums[j];
                if ((long)n1 + n2 > target && (long)n1 + n2 >= 0) {
                    break;
                }
                if (j > i + 1 && n2 == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.size() - 1;
                while (left < right) {
                    long sum = (long)n1 + n2 +nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        res.push_back(vector<int>{n1, n2, nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
};

C#

List/<IList/>的定义方式注意一下，不允许List/<List/<int//>>强转。

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        List<IList<int>> res = new List<IList<int>>();
        Array.Sort(nums);
        for (int i = 0; i < nums.Length - 3; i++) {
            int n1 = nums[i];
            if (n1 > target && n1 >= 0) break;
            if (i > 0 && n1 == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.Length - 2; j++) {
                int n2 = nums[j];
                if (n1 + n2 > target && n1 + n2 >= 0) break;
                if (j > i + 1 && n2 == nums[j - 1]) continue;
                int left = j + 1;
                int right = nums.Length - 1;
                while (left < right) {
                    long sum = (long)n1 + n2 + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        res.Add(new List<int>{n1, n2, nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) left++;
                        while (left < right && nums[right] == nums[right - 1]) right--;
                        left ++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
}

二刷

四数之和2

本题是独立的四个数组排列组合，并不需要考虑重复问题，与四数之和1不同，这是使用哈希方便的大前提。

注意两次双层循环，第二次找到目标ans累加的是map的value，对应n种组合。

  class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> data;
        for (int a : nums1) {
            for (int b : nums2) {
                data[a + b]++;
            }
        }
        int ans = 0;
        for (int c : nums3) {
            for (int d : nums4) {
                if (data.find(-(c + d)) != data.end()) {
                    ans += data[-(c + d)];
                }
            }
        } 
        return ans;
    }
};

赎金信

先记录一下magazine的字符出现次数，在遍历ransomeNote，如果没出现或者次数用光了都返回false。

  class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> data;
        for (char it : magazine) {
            data[it]++;
        }
        for (char it : ransomNote) {
            if (data.find(it) != data.end()) {
                data[it]--;
                if (data[it] == -1) {
                    return false;
                }
            } 
            else {
                return false;
            }
        }
        return true;
    }
};

15 三数之和

排序是为了适用双指针移动，对于每个i（第一个数），排序后left和right有且只有一种相加=0的情况（可能有重复，但去重了）
a去重要向前去，否则会把元素重复的情况剪去了，而题目只要求没有重复得三元组。
b和c去重要放在收获结果之后，否则有可能直接left和right相遇结果还没有收获。

  class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) return ans;
            //a去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right) {
                //左右指针移动
                if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                }
                if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                }
                if (left < right && nums[i] + nums[left] + nums[right] == 0) {
                    ans.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;  
                }
            }
        }
        return ans;
    }
};

四数之和

注意一下剪枝 >0 变成 >target;剪枝b的时候是> i + 1(向前剪枝留一位);四数相加会溢出用long。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > target && (nums[i] > 0 || target > 0)) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] > target && (nums[i] + nums[j] > 0 || target > 0)) break;
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1;
                int right = nums.size() - 1;
                while (left < right) {
                    if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target) right--;
                    else if ((long)nums[i] + nums[j] + nums[left] + nums[right] < target) left++;
                    else {
                        res.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
            }
        }
        return res;
    }
};

总结

哈希之前用C#的Dictionary挺多，哈希法有三类：数组，set，map，当题目有判断元素是否在集合中出现过，就要想到用哈希。

数组，哈希值范围确定，比如字母26个哈希值，相当于模拟map，优先选择。
set，只需要存是否有key，比如判断一个集合是否包含一个数。
map，不仅需要存key，还要存value，比如判断一个集合收包含一个数并存他出现的次数或者下标。

map，set各有三类，使用也有考究，如果是无序，不重复key用unordered_(map/set)，有序不重复用set/map,有序重复用multi_set/map，优先考虑使用unordered_(map/set)效率最高。实际上这两天的题只用了unordered，其他还需要练。

alt

三数之和，四数之和并不适用哈希，因为要对结果数组进行去重（哈希的话会很慢超时），双指针去重两步，先去遍历指针，再去left，right，二刷还需要多理解，同时看一下哈希去重到底麻烦在哪（三刷看吧hhhh）。

[代码随想录一刷＆二刷] day7 哈希表

四数相加II

C++

C#

赎金信

C++

C#

三数之和

C++

四数之和

C#

二刷

四数之和2

赎金信

15 三数之和

四数之和

总结