# Hash Table

## 49. Group Anagrams 群组错位词

Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter. 解法1 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]存不存在 m[t].push_back(str); } for (auto a : m) { res.

## 37. Sudoku Solver 求数独的一个解

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character ‘.

## 36. Valid Sudoku 验证数独

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.

## 30. Substring With Concatenation of All Words 串联所有单词的子串

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. For example, given: s: "barfoothefoobarman" words: ["foo", "bar"] You should return the indices: [0,9]. (order does not matter). Difficulty: Hard 这道题让我们求串联所有单词的子串.所有单词来自输入的数组.所有单词的长度一样,串联的顺序不一定.如题中的例子,可以串联成foobar, barfoo. 这里我们用两个哈希表,一个用来存输入单词数组的每个单词和其的出现次数.然后遍历输入的字符串.设单词的个数为n,每个单词长度为m.每次遍历检查母字符串从该位置开始,每m截取一下查看在第一个哈希表是否存在.如果存在,存入第二个哈希表.如果n个次截取都匹配则这次遍历是符合要求的,存一下结果. 解法1 就是上面分析 class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int>res; if (s.

## 18. 4Sum 四数之和

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] Difficulty: Medium

## Longest Substring Without Repeating Characters 子字符串的最大不重复长度

Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring. 滑动窗口问题,比如abcabcbb,滑动到abca的时候需要丢弃第一个a变成bca,继续向右滑动,每次滑动都要检查有没有重复.感觉涉及到最大,最多的问题都可以试着网哈希表上靠. class Solution { public: int lengthOfLongestSubstring(string s) { int size = s.

## Two Sum 两数之和等于一个输入的数

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums + nums = 2 + 7 = 9, return [0, 1]. 要返回数组中两个数的索引,这两个数的和等于输入的数.最简单的两层for循环可定不能满足要求.考虑优化时间复杂度,可尝试牺牲时间复杂度. stack?queue?vector?还是hash_map.stack,queue,vector查找都是O(n),hash_map为O(1).接下来尝试用hash_map解决问题. class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int>res; if(nums.