查找表相关的问题

梦里梦外; 2024-02-19 13:28 28阅读 0赞

349.[\[LeetCode\] Intersection of Two Arrays 两个数组相交][LeetCode_ Intersection of Two Arrays]

这道题让我们找两个数组交集的部分（不包含重复数字），难度不算大，我们可以用个set把nums1都放进去，然后遍历nums2的元素，如果在set中存在，说明是交集的部分，加入结果的set中，最后再把结果转为vector的形式即可：

解法一：

class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            set<int> s(nums1.begin(), nums1.end()), res;
            for (auto a : nums2) {
                if (s.count(a)) res.insert(a);
            }
            return vector<int>(res.begin(), res.end());
        }
    };

class Solution \{  
public:  
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) \{  
set<int>record;  
set<int>result;  
vector<int>re;  
for(int i=0;i<nums1.size();i++)  
record.insert(nums1\[i\]);  
for(int i=0;i<nums2.size();i++)  
if(record.find(nums2\[i\])!=record.end())  
result.insert(nums2\[i\]);  
//for(set<int>::iterator iter=result.begin();iter!=result.end();iter++)  
// re.push\_back(\*iter);  
return vector<int>(result.begin(),result.end());  
\}  
\};

350.[\[LeetCode\] Intersection of Two Arrays II 两个数组相交之二][LeetCode_ Intersection of Two Arrays II]

给定两个数组，编写一个函数来计算它们的交集。

**示例 1:**

输入: nums1 = [1,2,2,1], nums2 = [2,2]
    输出: [2,2]

**示例 2:**

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    输出: [4,9]

**说明：**

*  输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
 *  我们可以不考虑输出结果的顺序。

**进阶:**

*  如果给定的数组已经排好序呢？你将如何优化你的算法？
 *  如果 *nums1* 的大小比 *nums2* 小很多，哪种方法更优？
 *  如果 *nums2* 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

class Solution \{  
public:  
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) \{  
map<int,int>record;  
for(int i=0;i<nums1.size();i++)  
record\[nums1\[i\]\]++;  
vector<int>re;  
for(int i=0;i<nums2.size();i++)  
if(record\[nums2\[i\]\]>0)  
\{  
re.push\_back(nums2\[i\]);  
record\[nums2\[i\]\]--;  
\}  
return re;  
\}  
\};

set和map有不同的底层结构

242.[\[LeetCode\] Valid Anagram 验证变位词][LeetCode_ Valid Anagram]

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的一个字母异位词。

**示例 1:**

输入: s = "anagram", t = "nagaram"
    输出: true

**示例 2:**

输入: s = "rat", t = "car"
    输出: false

**说明:**  
你可以假设字符串只包含小写字母。

**进阶:**  
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

这不算一道难题，核心点就在于使用哈希表映射，我们还是用一个数组来代替哈希表，使用类似方法的题目有[Minimum Window Substring 最小窗口子串][Minimum Window Substring]，[Isomorphic Strings 同构字符串][Isomorphic Strings]，[Longest Substring Without Repeating Characters 最长无重复子串][Longest Substring Without Repeating Characters] 和 [1.1 Unique Characters of a String 字符串中不同的字符][1.1 Unique Characters of a String]。我们先判断两个字符串长度是否相同，不相同直接返回false。然后把s中所有的字符出现个数统计起来，存入一个大小为26的数组中，因为题目中限定了输入字符串为小写字母组成。然后我们再来统计t字符串，如果发现不匹配则返回false。 参见代码如下：

class Solution {
    public:
        bool isAnagram(string s, string t) {
            if (s.size() != t.size()) return false;
            int m[26] = {0};
            for (int i = 0; i < s.size(); ++i) ++m[s[i] - 'a'];
            for (int i = 0; i < t.size(); ++i) {
                if (--m[t[i] - 'a'] < 0) return false;
            }
            return true;
        }
    };

202.[\[LeetCode\] Happy Number 快乐数][LeetCode_ Happy Number]

编写一个算法来判断一个数是不是“快乐数”。

一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

**示例:**

输入: 19
    输出: true
    解释: 
    12 + 92 = 82
    82 + 22 = 68
    62 + 82 = 100
    12 + 02 + 02 = 1

这道题定义了一种快乐数，就是说对于某一个正整数，如果对其各个位上的数字分别平方，然后再加起来得到一个新的数字，再进行同样的操作，如果最终结果变成了1，则说明是快乐数，如果一直循环但不是1的话，就不是快乐数，那么现在任意给我们一个正整数，让我们判断这个数是不是快乐数，题目中给的例子19是快乐数，那么我们来看一个不是快乐数的情况，比如数字11有如下的计算过程：

1^2 + 1^2 = 2  
2^2 = 4  
4^2 = 16  
1^2 + 6^2 = 37  
3^2 + 7^2 = 58  
5^2 + 8^2 = 89  
8^2 + 9^2 = 145  
1^2 + 4^2 + 5^2 = 42  
4^2 + 2^2 = 20  
2^2 + 0^2 = 4

我们发现在算到最后时数字4又出现了，那么之后的数字又都会重复之前的顺序，这个循环中不包含1，那么数字11不是一个快乐数，发现了规律后就要考虑怎么用代码来实现，我们可以用set来记录所有出现过的数字，然后每出现一个新数字，在set中查找看是否存在，若不存在则加入表中，若存在则跳出循环，并且判断此数是否为1，若为1返回true，不为1返回false，代码如下：

解法一：

class Solution {
    public:
        bool isHappy(int n) {
            set<int> s;
            while (n != 1) {
                int t = 0;
                while (n) {
                    t += (n % 10) * (n % 10);
                    n /= 10;
                }
                n = t;
                if (s.count(n)) break;
                else s.insert(n);
            }
            return n == 1;
        }
    };

其实这道题也可以不用set来做，我们并不需要太多的额外空间，关于非快乐数有个特点，循环的数字中必定会有4，这里就不做证明了，我也不会证明，就是利用这个性质，就可以不用set了，参见代码如下：

解法二：

class Solution {
    public:
        bool isHappy(int n) {
            while (n != 1 && n != 4) {
                int t = 0;
                while (n) {
                    t += (n % 10) * (n % 10);
                    n /= 10;
                }
                n = t;
            }
            return n == 1;
        }
    };

290.[\[LeetCode\] Word Pattern 词语模式][LeetCode_ Word Pattern]

给定一种 `pattern(模式)` 和一个字符串 `str` ，判断 `str` 是否遵循相同的模式。

这里的**遵循**指完全匹配，例如， `pattern` 里的每个字母和字符串 `str`中的每个非空单词之间存在着双向连接的对应模式。

**示例1:**

输入: pattern = "abba", str = "dog cat cat dog"
    输出: true

**示例 2:**

输入:pattern = "abba", str = "dog cat cat fish"
    输出: false

**示例 3:**

输入: pattern = "aaaa", str = "dog cat cat dog"
    输出: false

**示例 4:**

输入: pattern = "abba", str = "dog dog dog dog"
    输出: false

**说明:**  
你可以假设 `pattern` 只包含小写字母， `str` 包含了由单个空格分隔的小写字母。

这道题给我们一个模式字符串，又给我们一个单词字符串，让我们求单词字符串中单词出现的规律是否符合模式字符串中的规律。那么首先想到就是用哈希表来做，建立模式字符串中每个字符和单词字符串每个单词之间的映射，而且这种映射必须是一对一关系的，不能'a‘和’b'同时对应‘dog'，所以我们在碰到一个新字符时，首先检查其是否在哈希表中出现，若出现，其映射的单词若不是此时对应的单词，则返回false。如果没有在哈希表中出现，我们还要遍历一遍哈希表，看新遇到的单词是否已经是哈希表中的映射，如果没有，再跟新遇到的字符建立映射，参见代码如下：

解法一：

![复制代码][copycode.gif]

class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            unordered_map<char, string> m;
            istringstream in(str);
            int i = 0;
            for (string word; in >> word; ++i) {
                if (m.find(pattern[i]) != m.end()) {
                    if (m[pattern[i]] != word) return false;
                } else {
                    for (unordered_map<char, string>::iterator it = m.begin(); it != m.end(); ++it) {
                        if (it->second == word) return false;
                    }
                    m[pattern[i]] = word;
                }
            }
            return i == pattern.size();
        }
    };

![复制代码][copycode.gif]

当然这道题也可以用两个哈希表来完成，分别将字符和单词都映射到当前的位置，那么我们在遇到新字符和单词时，首先看两个哈希表是否至少有一个映射存在，如果有一个存在，则比较两个哈希表映射值是否相同，不同则返回false。如果两个表都不存在映射，则同时添加两个映射，参见代码如下：

解法二：

![复制代码][copycode.gif]

class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            unordered_map<char, int> m1;
            unordered_map<string, int> m2;
            istringstream in(str);
            int i = 0;
            for (string word; in >> word; ++i) {
                if (m1.find(pattern[i]) != m1.end() || m2.find(word) != m2.end()) {
                    if (m1[pattern[i]] != m2[word]) return false;
                } else {
                    m1[pattern[i]] = m2[word] = i + 1;
                }
            }
            return i == pattern.size();
        }
    };

205.[\[LeetCode\] Isomorphic Strings 同构字符串][LeetCode_ Isomorphic Strings]

给定两个字符串 ***s*** 和 ***t***，判断它们是否是同构的。

如果 ***s*** 中的字符可以被替换得到 ***t*** ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

**示例 1:**

输入: s = "egg", t = "add"
    输出: true

**示例 2:**

输入: s = "foo", t = "bar"
    输出: false

**示例 3:**

输入: s = "paper", t = "title"
    输出: true

这道题让我们求同构字符串，就是说原字符串中的每个字符可由另外一个字符替代，可以被其本身替代，相同的字符一定要被同一个字符替代，且一个字符不能被多个字符替代，即不能出现一对多的映射。根据一对一映射的特点，我们需要用两个哈希表分别来记录原字符串和目标字符串中字符出现情况，由于ASCII码只有256个字符，所以我们可以用一个256大小的数组来代替哈希表，并初始化为0，我们遍历原字符串，分别从源字符串和目标字符串取出一个字符，然后分别在两个哈希表中查找其值，若不相等，则返回false，若相等，将其值更新为i + 1，因为默认的值是0，所以我们更新值为i + 1，这样当 i=0 时，则映射为1，如果不加1的话，那么就无法区分是否更新了，代码如下：

class Solution {
    public:
        bool isIsomorphic(string s, string t) {
            int m1[256] = {0}, m2[256] = {0}, n = s.size();
            for (int i = 0; i < n; ++i) {
                if (m1[s[i]] != m2[t[i]]) return false;
                m1[s[i]] = i + 1;
                m2[t[i]] = i + 1;
            }
            return true;
        }
    };

451.[\[LeetCode\] Sort Characters By Frequency 根据字符出现频率排序][LeetCode_ Sort Characters By Frequency]

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

**示例 1:**

输入:
    "tree"
    
    输出:
    "eert"
    
    解释:
    'e'出现两次，'r'和't'都只出现一次。
    因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

**示例 2:**

输入:
    "cccaaa"
    
    输出:
    "cccaaa"
    
    解释:
    'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
    注意"cacaca"是不正确的，因为相同的字母必须放在一起。

**示例 3:**

输入:
    "Aabb"
    
    输出:
    "bbAa"
    
    解释:
    此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
    注意'A'和'a'被认为是两种不同的字符。

这道题让我们给一个字符串按照字符出现的频率来排序，那么毫无疑问肯定要先统计出每个字符出现的个数，那么之后怎么做呢？我们可以利用优先队列的自动排序的特点，把个数和字符组成pair放到优先队列里排好序后，再取出来组成结果res即可，参见代码如下：

解法一：

class Solution {
    public:
        string frequencySort(string s) {
            string res = "";
            priority_queue<pair<int, char>> q;
            unordered_map<char, int> m;
            for (char c : s) ++m[c];
            for (auto a : m) q.push({a.second, a.first});
            while (!q.empty()) {
                auto t = q.top(); q.pop();
                res.append(t.first, t.second);
            }
            return res;
        }
    };

我们也可以使用STL自带的sort来做，关键就在于重写comparator，由于需要使用外部变量，记得中括号中放入＆，然后我们将频率大的返回，注意一定还要处理频率相等的情况，要不然两个频率相等的字符可能穿插着出现在结果res中，这样是不对的。参见代码如下：

解法二：

![复制代码][copycode.gif]

class Solution {
    public:
        string frequencySort(string s) {
            unordered_map<char, int> m;
            for (char c : s) ++m[c];
            sort(s.begin(), s.end(), [&](char& a, char& b){
                return m[a] > m[b] || (m[a] == m[b] && a < b);
            });
            return s;
        }
    };

我们也可以不使用优先队列，而是建立一个字符串数组，因为某个字符的出现次数不可能超过s的长度，所以我们将每个字符根据其出现次数放入数组中的对应位置，那么最后我们只要从后往前遍历数组所有位置，将不为空的位置的字符串加入结果res中即可，参见代码如下：

解法三：

class Solution {
    public:
        string frequencySort(string s) {
            string res = "";
            vector<string> v(s.size() + 1, "");
            unordered_map<char, int> m;
            for (char c : s) ++m[c];
            for (auto& a : m) {
                v[a.second].append(a.second, a.first);
            }
            for (int i = s.size(); i > 0; --i) {
                if (!v[i].empty()) {
                    res.append(v[i]);
                }
            }
            return res;
        }
    };

1.[\[LeetCode\] Two Sum 两数之和][LeetCode_ Two Sum]

给定一个整数数组和一个目标值，找出数组中和为目标值的**两个**数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

**示例:**

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

使用一个HashMap，来建立数字和其坐标位置之间的映射，我们都知道HashMap是常数级的查找效率，这样，我们在遍历数组的时候，用target减去遍历到的数字，就是另一个需要的数字了，直接在HashMap中查找其是否存在即可，注意要判断查找到的数字不是第一个数字，比如target是4，遍历到了一个2，那么另外一个2不能是之前那个2，整个实现步骤为：先遍历一遍数组，建立HashMap映射，然后再遍历一遍，开始查找，找到则记录index。代码如下：

C++ 解法一：

![复制代码][copycode.gif]

class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            unordered_map<int,int>record;
            for(int i=0;i<nums.size();i++)
            {
                int com=target-nums[i];
                if(record.find(com)!=record.end())
                {
                    int res[2]={i,record[com]};
                return vector<int>(res,res+2);
                }
                record[nums[i]]=i;
            }
            
        }
        
    };

15.[\[LeetCode\] 3Sum 三数之和][LeetCode_ 3Sum]

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

。那么我们来分析一下这道题的特点，要我们找出三个数且和为0，那么除了三个数全是0的情况之外，肯定会有负数和正数，我们还是要先fix一个数，然后去找另外两个数，我们只要找到两个数且和为第一个fix数的相反数就行了，既然另外两个数不能使用[Two Sum][]的那种解法来找，如果能更有效的定位呢？我们肯定不希望遍历所有两个数的组合吧，所以如果数组是有序的，那么我们就可以用双指针以线性时间复杂度来遍历所有满足题意的两个数组合。

我们对原数组进行排序，然后开始遍历排序后的数组，这里注意不是遍历到最后一个停止，而是到倒数第三个就可以了。这里我们可以先做个剪枝优化，就是当遍历到正数的时候就break，为啥呢，因为我们的数组现在是有序的了，如果第一个要fix的数就是正数了，那么后面的数字就都是正数，就永远不会出现和为0的情况了。然后我们还要加上重复就跳过的处理，处理方法是从第二个数开始，如果和前面的数字相等，就跳过，因为我们不想把相同的数字fix两次。对于遍历到的数，用0减去这个fix的数得到一个target，然后只需要再之后找到两个数之和等于target即可。我们用两个指针分别指向fix数字之后开始的数组首尾两个数，如果两个数和正好为target，则将这两个数和fix的数一起存入结果中。然后就是跳过重复数字的步骤了，两个指针都需要检测重复数字。如果两数之和小于target，则我们将左边那个指针i右移一位，使得指向的数字增大一些。同理，如果两数之和大于target，则我们将右边那个指针j左移一位，使得指向的数字减小一些，代码如下：

解法一：

![复制代码][copycode.gif]

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

或者我们也可以利用set的不能包含重复项的特点来防止重复项的产生，那么我们就不需要检测数字是否被fix过两次，不过个人觉得还是前面那种解法更好一些，参见代码如下：

解法二：

class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            set<vector<int>> res;
            sort(nums.begin(), nums.end());
            if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {};
            for (int k = 0; k < nums.size(); ++k) {
                if (nums[k] > 0) break;
                int target = 0 - nums[k];
                int i = k + 1, j = nums.size() - 1;
                while (i < j) {
                    if (nums[i] + nums[j] == target) {
                        res.insert({nums[k], nums[i], nums[j]});
                        while (i < j && nums[i] == nums[i + 1]) ++i;
                        while (i < j && nums[j] == nums[j - 1]) --j;
                        ++i; --j;
                    } else if (nums[i] + nums[j] < target) ++i;
                    else --j;
                }
            }
            return vector<vector<int>>(res.begin(), res.end());
        }
    };

18.[\[LeetC][LeetC][ode\] 4Sum 四数之和][LeetC]

给定一个包含 *n* 个整数的数组 `nums` 和一个目标值 `target`，判断 `nums` 中是否存在四个元素 *a，**b，c* 和 *d* ，使得 *a* \+ *b* \+ *c* \+ *d* 的值与 `target` 相等？找出所有满足条件且不重复的四元组。

**注意：**

答案中不可以包含重复的四元组。

**示例：**

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
    
    满足要求的四元组集合为：
    [
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]

在这里为了避免重复项，我们使用了STL中的set，其特点是不能有重复，如果新加入的数在set中原本就存在的话，插入操作就会失败，这样能很好的避免的重复项的存在。此题的O(n^3)解法的思路跟[3Sum 三数之和][3Sum]基本没啥区别，就是多加了一层for循环，其他的都一样，代码如下：

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

16.[\[LeetCode\] 3Sum Closest 最近三数之和][LeetCode_ 3Sum Closest]

给定一个包括 *n* 个整数的数组 `nums`和 一个目标值 `target`。找出 `nums`中的三个整数，使得它们的和与 `target` 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
    
    与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

这道题让我们求最接近给定值的三数之和，是在之前那道[ 3Sum 三数之和][3Sum]的基础上又增加了些许难度，那么这道题让我们返回这个最接近于给定值的值，即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量diff用来记录差的绝对值，然后我们还是要先将数组排个序，然后开始遍历数组，思路跟那道三数之和很相似，都是先确定一个数，然后用两个指针left和right来滑动寻找另外两个数，每确定两个数，我们求出此三数之和，然后算和给定值的差的绝对值存在newDiff中，然后和diff比较并更新diff和结果closest即可，代码如下：

class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            int closest = nums[0] + nums[1] + nums[2];
            int diff = abs(closest - target);
            sort(nums.begin(), nums.end());
            for (int i = 0; i < nums.size() - 2; ++i) {
                int left = i + 1, right = nums.size() - 1;
                while (left < right) {
                    int sum = nums[i] + nums[left] + nums[right];
                    int newDiff = abs(sum - target);
                    if (diff > newDiff) {
                        diff = newDiff;
                        closest = sum;
                    }
                    if (sum < target) ++left;
                    else --right;
                }
            }
            return closest;
        }
    };

454.[\[LeetCode\] 4Sum II 四数之和之二][LeetCode_ 4Sum II]

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 `(i, j, k, l)` ，使得 `A[i] + B[j] + C[k] + D[l] = 0`。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

**例如:**

输入:
    A = [ 1, 2]
    B = [-2,-1]
    C = [-1, 2]
    D = [ 0, 2]
    
    输出:
    2
    
    解释:
    两个元组如下:
    1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
    2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

class Solution \{  
public:  
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) \{  
unordered\_map<int,int>record;  
for(int i=0;i<C.size();i++)  
for(int j=0;j<D.size();j++)  
record\[C\[i\]+D\[j\]\]++;  
int res=0;  
for(int i=0;i<A.size();i++)  
for(int j=0;j<B.size();j++)  
if(record.find(0-A\[i\]-B\[j\])!=record.end())  
res+=record\[0-A\[i\]-B\[j\]\];  
return res;  
\}  
\};

49.[\[LeetCode\] Group Anagrams 群组错位词][LeetCode_ Group Anagrams]

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

**示例:**

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
    输出:
    [
      ["ate","eat","tea"],
      ["nat","tan"],
      ["bat"]
    ]

**说明：**

*  所有输入均为小写字母。
 *  不考虑答案输出的顺序。

这道题让我们群组给定字符串集中所有的错位词，所谓的错位词就是两个字符串中字母出现的次数都一样，只是位置不同，比如abc，bac, cba等它们就互为错位词，那么我们如何判断两者是否是错位词呢，我们发现如果把错位词的字符顺序重新排列，那么会得到相同的结果，所以重新排序是判断是否互为错位词的方法，由于错位词重新排序后都会得到相同的字符串，我们以此作为key，将所有错位词都保存到字符串数组中，建立key和字符串数组之间的映射，最后再存入结果res中即可，擦巾代码如下：

解法一：

class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            vector<vector<string>> res;
            unordered_map<string, vector<string>> m;
            for (string str : strs) {
                string t = str;
                sort(t.begin(), t.end());
                m[t].push_back(str);
            }
            for (auto a : m) {
                res.push_back(a.second);
            }
            return res;
        }
    };

下面这种解法没有用到排序，提高了运算效率，我们用一个大小为26的int数组来统计每个单词中字符出现的次数，然后将int数组转为一个唯一的字符串，跟字符串数组进行映射，这样我们就不用给字符串排序了，代码如下：

解法二：

![复制代码][copycode.gif]

class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            vector<vector<string>> res;
            unordered_map<string, vector<string>> m;
            for (string str : strs) {
                vector<int> cnt(26, 0);
                string t = "";
                for (char c : str) ++cnt[c - 'a'];
                for (int d : cnt) t += to_string(d) + "/";
                m[t].push_back(str);
            }
            for (auto a : m) {
                res.push_back(a.second);
            }
            return res;
        }
    };

447.[\[LeetCode\] Number of Boomerangs 回旋镖的数量][LeetCode_ Number of Boomerangs]

给定平面上 *n* 对不同的点，“回旋镖” 是由点表示的元组 `(i, j, k)` ，其中 `i` 和 `j` 之间的距离和 `i` 和 `k` 之间的距离相等（**需要考虑元组的顺序**）。

找到所有回旋镖的数量。你可以假设 *n* 最大为 **500**，所有点的坐标在闭区间 **\[-10000, 10000\]** 中。

**示例:**

输入:
    [[0,0],[1,0],[2,0]]
    
    输出:
    2
    
    解释:
    两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

这道题定义了一种类似回旋镖形状的三元组结构，要求第一个点和第二个点之间的距离跟第一个点和第三个点之间的距离相等。现在给了我们n个点，让我们找出回旋镖的个数。那么我们想，如果我们有一个点a，还有两个点b和c，如果ab和ac之间的距离相等，那么就有两种排列方法abc和acb；如果有三个点b，c，d都分别和a之间的距离相等，那么有六种排列方法，abc, acb, acd, adc, abd, adb，那么是怎么算出来的呢，很简单，如果有n个点和a距离相等，那么排列方式为n(n-1)，这属于最简单的排列组合问题了，我大天朝中学生都会做的。那么我们问题就变成了遍历所有点，让每个点都做一次点a，然后遍历其他所有点，统计和a距离相等的点有多少个，然后分别带入n(n-1)计算结果并累加到res中，只有当n大于等于2时，res值才会真正增加，参见代码如下：

![复制代码][copycode.gif]

class Solution {
    public:
        int numberOfBoomerangs(vector<pair<int, int>>& points) {
            int res = 0;
            for (int i = 0; i < points.size(); ++i) {
                unordered_map<int, int> m;
                for (int j = 0; j < points.size(); ++j) {
                    int a = points[i].first - points[j].first;
                    int b = points[i].second - points[j].second;
                    ++m[a * a + b * b];
                }
                for (auto it = m.begin(); it != m.end(); ++it) {
                    res += it->second * (it->second - 1);
                }
            }
            return res;
        }
    };

class Solution \{  
public:  
int numberOfBoomerangs(vector<pair<int, int>>& points) \{  
int res=0;  
for(int i=0;i<points.size();i++)  
\{  
unordered\_map<int,int>record;  
for(int j=0;j<points.size();j++)  
if(j!=i)  
record\[dis(points\[i\],points\[j\])\]++;  
for(unordered\_map<int,int>::iterator iter=record.begin();iter!=record.end();iter++)  
if(iter->second>=2)  
res+=(iter->second)\*(iter->second-1);  
\}  
return res;  
\}  
private:  
int dis(const pair<int,int>&pa,const pair<int,int>&pb)  
\{  
return (pa.first-pb.first)\*(pa.first-pb.first)+(pa.second-pb.second)\*(pa.second-pb.second);  
  
\}  
\};

149.[\[LeetCode\] Max Points on a Line 共线点个数][LeetCode_ Max Points on a Line]

这道题给了我们一堆二维点，然后让我们求最大的共线点的个数，根据初中数学我们知道，两点确定一条直线，而且可以写成y = ax + b的形式，所有共线的点都满足这个公式。所以这些给定点两两之间都可以算一个斜率，每个斜率代表一条直线，对每一条直线，带入所有的点看是否共线并计算个数，这是整体的思路。但是还有两点特殊情况需要考虑，二是当两个点重合时，无法确定一条直线，但这也是共线的情况，需要特殊处理。二是斜率不存在的情况，由于两个点(x1, y1)和(x2, y2)的斜率k表示为(y2 - y1) / (x2 - x1)，那么当x1 = x2时斜率不存在，这种共线情况需要特殊处理。我们需要用到哈希表来记录斜率和共线点个数之间的映射，其中第一种重合点的情况我们假定其斜率为INT\_MIN，第二种情况我们假定其斜率为INT\_MAX，这样都可以用map映射了。我们还需要顶一个变量duplicate来记录重合点的个数，最后只需和哈希表中的数字相加即为共线点的总数，这种方法现在已经无法通过OJ了，贴出来权当纪念。代码如下：

C++ 解法一：

![复制代码][copycode.gif]

// Failed on case: [[0,0],[94911151,94911150],[94911152,94911151]]
    class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            int res = 0;
            for (int i = 0; i < points.size(); ++i) {
                unordered_map<float, int> m;
                int duplicate = 1;
                for (int j = i + 1; j < points.size(); ++j) {
                    if (points[i].x == points[j].x && points[i].y == points[j].y) {
                        ++duplicate;
                    } else if (points[i].x == points[j].x) {
                        ++m[INT_MAX];
                    } else {
                        float slope = (float)(points[j].y - points[i].y) / (points[j].x - points[i].x);
                        ++m[slope];
                    }
                }
                res = max(res, duplicate);
                for (auto it = m.begin(); it != m.end(); ++it) {
                    res = max(res, it->second + duplicate);
                }
            }
            return res;
        }
    };

由于通过斜率来判断共线需要用到除法，而用double表示的双精度小数在有的系统里不一定准确，为了更加精确无误的计算共线，我们应当避免除法，从而避免无线不循环小数的出现，那么怎么办呢，我们把除数和被除数都保存下来，不做除法，但是我们要让这两数分别除以它们的最大公约数，这样例如8和4，4和2，2和1，这三组商相同的数就都会存到一个映射里面，同样也能实现我们的目标，而求GCD的函数如果用递归来写那么一行就搞定了，叼不叼，这个方法能很好的避免除法的出现，算是牺牲了空间来保证精度吧，参见代码如下：

C++ 解法二：

![复制代码][copycode.gif]

class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            int res = 0;
            for (int i = 0; i < points.size(); ++i) {
                map<pair<int, int>, int> m;
                int duplicate = 1;
                for (int j = i + 1; j < points.size(); ++j) {
                    if (points[i].x == points[j].x && points[i].y == points[j].y) {
                        ++duplicate; continue;
                    } 
                    int dx = points[j].x - points[i].x;
                    int dy = points[j].y - points[i].y;
                    int d = gcd(dx, dy);
                    ++m[{dx / d, dy / d}];
                }
                res = max(res, duplicate);
                for (auto it = m.begin(); it != m.end(); ++it) {
                    res = max(res, it->second + duplicate);
                }
            }
            return res;
        }
        int gcd(int a, int b) {
            return (b == 0) ? a : gcd(b, a % b);
        }
    };

令我惊奇的是，这道题的OJ居然容忍brute force的方法通过，那么我感觉下面这种O(n3)的解法之所以能通过OJ，可能还有一个原因就是用了比较高效的判断三点共线的方法。一般来说判断三点共线有三种方法，斜率法，周长法，面积法(请参见[这个帖子][Link 1])。而其中通过判断叉积为零的面积法是坠好的。比如说有三个点A(x1, y1)、B(x2, y2)、C(x3, y3)，那么判断三点共线就是判断下面这个等式是否成立：

![391947-20170111141450088-1765227618.jpg][]

行列式的求法不用多说吧，不会的话回去翻线性代数，当初少打点刀塔不就好啦~

C++ 解法三：

![复制代码][copycode.gif]

class Solution {
    public:
        int maxPoints(vector<Point>& points) {
            int res = 0;
            for (int i = 0; i < points.size(); ++i) {
                int duplicate = 1;
                for (int j = i + 1; j < points.size(); ++j) {
                    int cnt = 0;
                    long long x1 = points[i].x, y1 = points[i].y;
                    long long x2 = points[j].x, y2 = points[j].y;
                    if (x1 == x2 && y1 == y2) {++duplicate; continue;}
                    for (int k = 0; k < points.size(); ++k) {
                        int x3 = points[k].x, y3 = points[k].y;
                        if (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3 == 0) {
                            ++cnt;
                        }
                    }
                    res = max(res, cnt);
                }
                res = max(res, duplicate);
            }
            return res;
        }
    };

219.[\[LeetCode\] Contains Duplicate II 包含重复值之二][LeetCode_ Contains Duplicate II]

给定一个整数数组和一个整数 *k*，判断数组中是否存在两个不同的索引 *i* 和 *j*，使得 **nums \[i\] = nums \[j\]**，并且 *i* 和 *j* 的差的绝对值最大为 *k*。

**示例 1:**

输入: nums = [1,2,3,1], k = 3
    输出: true

**示例 2:**

输入: nums = [1,0,1,1], k = 1
    输出: true

**示例 3:**

输入: nums = [1,2,3,1,2,3], k = 2
    输出: false

这道题是之前那道[Contains Duplicate 包含重复值][Contains Duplicate]的延伸，不同之处在于那道题只要我们判断下数组中是否有重复值，而这道题限制了数组中只许有一组重复的数字，而且他们坐标差不能超过k。那么我们首先需要一个哈希表，来记录每个数字和其坐标的映射，然后我们需要一个变量d来记录第一次出现重复数字的坐标差。由于题目要求只能有一组重复的数字，所以我们在遇到重复数字时，首先判断d是否已经存了值，如果d已经有值了，说明之前有过了重复数字，则直接返回false即可。如果没有，则此时给d附上值。在网上看到有些解法在这里就直接判断d和k的关系然后返回结果了，其实这样是不对的。因为题目要求只能有一组重复数，就是说如果后面又出现了重复数，就没法继续判断了。所以正确的做法应该是扫描完整个数组后在判断，先看d有没有存入结果，如果没有，则说明没出现过重复数， 返回false即可。如果d有值，再跟k比较，返回对应的结果。OJ的test case没有包含所有的情况，比如当nums = \[1, 2, 3, 1, 3\], k = 3时，实际上应该返回false，但是有些返回true的算法也能通过OJ。个人认为正确的解法应该入下：

![复制代码][copycode.gif]

// Wrong Soulution
    class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            unordered_map<int, int> m;
            int d = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (m.find(nums[i]) != m.end()) {
                    if (d > 0) return false;
                    d = i - m[nums[i]];
                }
                m[nums[i]] = i;
            }
            return d == 0 ? false : d <= k;
        }
    };

![复制代码][copycode.gif]

坑爹啊，题目要求变了，那么就没啥歧义了，正确解法如下：

class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            unordered_map<int, int> m;
            for (int i = 0; i < nums.size(); ++i) {
                if (m.find(nums[i]) != m.end() && i - m[nums[i]] <= k) return true;
                else m[nums[i]] = i;
            }
            return false;
        }
    };

217.[\[LeetCode\] Contains Duplicate 包含重复值][LeetCode_ Contains Duplicate]

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

**示例 1:**

输入: [1,2,3,1]
    输出: true

**示例 2:**

输入: [1,2,3,4]
    输出: false

**示例 3:**

输入: [1,1,1,3,3,4,3,2,4,2]
    输出: true

这道题不算难题，就是使用一个哈希表，遍历整个数组，如果哈希表里存在，返回false，如果不存在，则将其放入哈希表中，代码如下：

解法一

![复制代码][copycode.gif]

class Solution {
    public:
        bool containsDuplicate(vector<int>& nums) {
            unordered_map<int, int> m;
            for (int i = 0; i < nums.size(); ++i) {
                if (m.find(nums[i]) != m.end()) return true;
                ++m[nums[i]];
            }
            return false;
        }
    };

![复制代码][copycode.gif]

这题还有另一种解法，就是先将数组排个序，然后再比较相邻两个数字是否相等，时间复杂度取决于排序方法，代码如下：

解法二

![复制代码][copycode.gif]

class Solution {
    public:
        bool containsDuplicate(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            for (int i = 1; i < nums.size(); ++i) {
                if (nums[i] == nums[i - 1]) return true;
            }
            return false;
        }
    };

220.[\[LeetCode\] Contains Duplicate III 包含重复值之三][LeetCode_ Contains Duplicate III]

给定一个整数数组，判断数组中是否有两个不同的索引 *i* 和 *j*，使得 **nums \[i\]** 和 **nums \[j\]** 的差的绝对值最大为 *t*，并且 *i* 和 *j* 之间的差的绝对值最大为 *ķ*。

**示例 1:**

输入: nums = [1,2,3,1], k = 3, t = 0
    输出: true

**示例 2:**

输入: nums = [1,0,1,1], k = 1, t = 2
    输出: true

**示例 3:**

输入: nums = [1,5,9,1,5,9], k = 2, t = 3
    输出: false

lower\_bound( )和upper\_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

在从小到大的排序数组中，

lower\_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper\_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

这道题跟之前两道[Contains Duplicate 包含重复值][Contains Duplicate]和[Contains Duplicate II 包含重复值之二][Contains Duplicate II]的关联并不是很大，前两道起码跟重复值有关，这道题的焦点不是在重复值上面，反而是关注与不同的值之间的关系，这里有两个限制条件，两个数字的坐标差不能大于k，值差不能大于t。这道题如果用brute force会超时，所以我们只能另辟蹊径。这里我们使用map数据结构来解,用来记录数字和其下标之间的映射。 这里需要两个指针i和j，刚开始i和j都指向0，然后i开始向右走遍历数组，如果i和j之差大于k，且m中有nums\[j\]，则删除并j加一。这样保证了m中所有的数的下标之差都不大于k，然后我们用map数据结构的lower\_bound()函数来找一个特定范围，就是大于或等于nums\[i\] - t的地方，所有小于这个阈值的数和nums\[i\]的差的绝对值会大于t (可自行带数检验)。然后检测后面的所有的数字，如果数的差的绝对值小于等于t，则返回true。最后遍历完整个数组返回false。代码如下：

![复制代码][copycode.gif]

class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            map<long long, int> m;
            int j = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (i - j > k) m.erase(nums[j++]);
                auto a = m.lower_bound((long long)nums[i] - t);
                if (a != m.end() && abs(a->first - nums[i]) <= t) return true;
                m[nums[i]] = i;
            }
            return false;
        }
    };

class Solution \{  
public:  
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) \{  
set<long long>record;  
for(int i=0;i<nums.size();i++)  
\{  
if(record.lower\_bound((long long)nums\[i\]-(long long)t)!=record.end()&&\*record.lower\_bound((long long)nums\[i\]-(long long)t)<=(long long )nums\[i\]+(long long)t)  
return true;  
record.insert(nums\[i\]);  
if(record.size()==k+1)  
record.erase(nums\[i-k\]);  
\}  
return false;  
\}  
\};

[LeetCode_ Intersection of Two Arrays]: https://www.cnblogs.com/grandyang/p/5507129.html
[LeetCode_ Intersection of Two Arrays II]: https://www.cnblogs.com/grandyang/p/5533305.html
[LeetCode_ Valid Anagram]: https://www.cnblogs.com/grandyang/p/4694988.html
[Minimum Window Substring]: http://www.cnblogs.com/grandyang/p/4340948.html
[Isomorphic Strings]: http://www.cnblogs.com/grandyang/p/4465779.html
[Longest Substring Without Repeating Characters]: http://www.cnblogs.com/grandyang/p/4480780.html
[1.1 Unique Characters of a String]: http://www.cnblogs.com/grandyang/p/4648044.html
[LeetCode_ Happy Number]: https://www.cnblogs.com/grandyang/p/4447233.html
[LeetCode_ Word Pattern]: https://www.cnblogs.com/grandyang/p/4857022.html
[copycode.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/8617b07326b44a459ad86833e7289925.png
[LeetCode_ Isomorphic Strings]: https://www.cnblogs.com/grandyang/p/4465779.html
[LeetCode_ Sort Characters By Frequency]: https://www.cnblogs.com/grandyang/p/6231504.html
[LeetCode_ Two Sum]: https://www.cnblogs.com/grandyang/p/4130379.html
[LeetCode_ 3Sum]: https://www.cnblogs.com/grandyang/p/4481576.html
[Two Sum]: http://www.cnblogs.com/grandyang/p/4130379.html
[LeetC]: https://www.cnblogs.com/grandyang/p/4515925.html
[3Sum]: http://www.cnblogs.com/grandyang/p/4481576.html
[LeetCode_ 3Sum Closest]: https://www.cnblogs.com/grandyang/p/4510984.html
[LeetCode_ 4Sum II]: https://www.cnblogs.com/grandyang/p/6073317.html
[LeetCode_ Group Anagrams]: https://www.cnblogs.com/grandyang/p/4385822.html
[LeetCode_ Number of Boomerangs]: https://www.cnblogs.com/grandyang/p/6049382.html
[LeetCode_ Max Points on a Line]: https://www.cnblogs.com/grandyang/p/4579693.html
[Link 1]: http://yiminghe.iteye.com/blog/568666
[391947-20170111141450088-1765227618.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c67ba4fd80574662b5e1a4ad721204c3.png
[LeetCode_ Contains Duplicate II]: https://www.cnblogs.com/grandyang/p/4539680.html
[Contains Duplicate]: http://www.cnblogs.com/grandyang/p/4537029.html
[LeetCode_ Contains Duplicate]: https://www.cnblogs.com/grandyang/p/4537029.html
[LeetCode_ Contains Duplicate III]: https://www.cnblogs.com/grandyang/p/4545261.html
[Contains Duplicate II]: http://www.cnblogs.com/grandyang/p/4539680.html