查找，是使用计算机处理问题时的一个最基本的任务，因此也是面试中非常常见的一类问题。很多算法问题的本质，就是要能够高效查找。学会使用系统库中的map和set，就已经成功了一半。

set的使用:

问题1：Intersection of Two Arrays

原题
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

/// Hash Set
/// Time complexity: O(len(nums1) + len(nums2))
/// Space Complexity: O(len(nums1))
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

        unordered_set<int> record(nums1.begin(), nums1.end());

        unordered_set<int> resultSet;
        for( int i = 0 ; i < nums2.size() ; i ++ )
            if( record.find(nums2[i]) != record.end() )
                resultSet.insert( nums2[i] );

        return vector<int>(resultSet.begin(), resultSet.end());
    }
};

map的使用:

问题2：Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

map和set的底层实现为平衡二叉树，unordered_map和set的底层实现为哈希表

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;


/// Using Hash Map
/// Time Complexity: O(len(nums1) + len(nums2))
/// Space Complexity: O(len(nums1))
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

        unordered_map<int, int> record;  //记录频次
        for(int i = 0 ; i < nums1.size() ; i ++)
            record[nums1[i]] += 1;

        vector<int> resultVector;
        for(int i = 0 ; i < nums2.size() ; i ++)
            if(record[nums2[i]] > 0){
                resultVector.push_back(nums2[i]);
                record[nums2[i]] --;
            }

        return resultVector;
    }
};

问题3：Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.
Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true
Example 2:
Input: s = “rat”, t = “car”
Output: false

using namespace std;

/// Sorting
/// Time Complexity: O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    bool isAnagram(string s, string t) {

        sort(s.begin(), s.end());
        sort(t.begin(), t.end());

        return s == t;
    }
};

问题4：Valid Anagram:Word Pattern

原题
Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.
Example 1:
Input: pattern = “abba”, str = “dog cat cat dog”
Output: true
Example 2:
Input:pattern = “abba”, str = “dog cat cat fish”
Output: false
Example 3:
Input: pattern = “aaaa”, str = “dog cat cat dog”
Output: false
Example 4:
Input: pattern = “abba”, str = “dog dog dog dog”
Output: false

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>

using namespace std;


/// HashMap
/// TimeComplexity: O(n)
/// Space Complexity: O(n)
class Solution {

public:
    bool wordPattern(string pattern, string str) {

        vector<string> words = split(str);  //保存str字符串
        if(pattern.size() != words.size())
            return false;

        unordered_map<char, string> map1;
        unordered_map<string, char> map2;
        for(int i = 0 ; i < pattern.size() ; i++)
            if(map1.find(pattern[i]) == map1.end()){
                if(map2.find(words[i]) != map2.end())
                    return false;
                map1[pattern[i]] = words[i];
                map2[words[i]] = pattern[i];
            }
            else{
                string s = map1[pattern[i]];
                if(s != words[i])
                    return false;
            }

        return true;
    }

private:
    vector<string> split(const string& s){

        vector<string> res;
        int start = 0;
        for(int i = start + 1 ; i <= s.size() ; )
            if(i == s.size() || s[i] == ' '){
                res.push_back(s.substr(start, i - start));
                start = i + 1;
                i = start + 1;
            }
            else
                i ++;
        return res;
    }
};

问题5：Isomorphic Strings

原题
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
Example 1:
Input: s = “egg”, t = “add”
Output: true
Example 2:
Input: s = “foo”, t = “bar”
Output: false
Example 3:
Input: s = “paper”, t = “title”
Output: true
思路
用一个哈希表记录字符串s中字母到字符串t中字母的映射关系，一个集合记录已经映射过的字母。或者用两个哈希表记录双向的映射关系。这里不能只用一个哈希表，因为要排除egg->ddd这种多对一的映射。

#include <iostream>
#include <cstring>

using namespace std;

/// Mapping
/// Time Complexity: O(len(s))
/// Space Complexity: O(len of charset)
class Solution {
public:
    bool isIsomorphic(string s, string t) {

        if(s.size() != t.size())
            return false;

        int map[256];
        memset(map, -1, sizeof(map));

        bool mapped[256];
        memset(mapped, false, sizeof(mapped));

        for(int i = 0 ; i < s.size() ; i ++){
            if(map[s[i]] == -1){ //判断s[i]是否已经映射过
                if(mapped[t[i]])  //判断t[i]是否被映射
                    return false;
                map[s[i]] = t[i];
                mapped[t[i]] = true; //已经映射过了
            }
            else if(map[s[i]] != t[i])
                return false;
        }
        return true;
    }
};

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> map = new HashMap<Character, Character>();
        Set<Character> set = new HashSet<Character>();
        if(s.length() != t.length()) return false;
        for(int i = 0; i < s.length(); i++){
            char sc = s.charAt(i), tc = t.charAt(i);
            if(map.containsKey(sc)){
                // 如果已经给s中的字符建立了映射，检查该映射是否和当前t中字符相同
                if(tc != map.get(sc)) return false;
            } else {
                // 如果已经给t中的字符建立了映射，就返回假，因为出现了多对一映射
                if(set.contains(tc)) return false;
                map.put(sc, tc);
                set.add(tc);
            }
        }
        return true;
    }
}

问题6：Isomorphic Strings

原题
Given a string, sort it in decreasing order based on the frequency of characters.
Example 1:
Input:
“tree”
Output:
“eert”
Explanation:
‘e’ appears twice while ‘r’ and ‘t’ both appear once.
So ‘e’ must appear before both ‘r’ and ‘t’. Therefore “eetr” is also a valid answer.
Example 2:
Input:
“cccaaa”
Output:
“cccaaa”
Explanation:
Both ‘c’ and ‘a’ appear three times, so “aaaccc” is also a valid answer.
Note that “cacaca” is incorrect, as the same characters must be together.
Example 3:
Input:
“Aabb”
Output:
“bbAa”
Explanation:
“bbaA” is also a valid answer, but “Aabb” is incorrect.
Note that ‘A’ and ‘a’ are treated as two different characters.

#include <iostream>

using namespace std;

/// Using Counting Sort
/// Time Complexity: O(n)
/// Space Complexity: O(256)
class Solution {
public:
    string frequencySort(string s) {

        pair<int, char> freq[256];
        for(int i = 0 ; i < 256 ; i ++){
            freq[i].first = 0;
            freq[i].second = i;
        }

        for(int i = 0 ; i < s.size() ; i ++)
            freq[s[i]].first ++;

        sort(freq, freq + 256, greater<pair<int, char>>());//利用排序，频率大的先返回

        int index = 0;
        for(int i = 0 ; i < s.size() ; i ++){
            while(!freq[index].first)
                index ++;
            s[i] = freq[index].second;
            freq[index].first --;
        }

        return s;
    }
};

使用查找表的经典问题 :

问题7：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[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

#include <iostream>
#include <vector>
#include <cassert>
#include <unordered_map>

using namespace std;


/// One-Pass Hash Table
/// Time Complexity: O(n)
/// Space Complexity: O(n)
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 complement = target - nums[i];
            if(record.find(complement) != record.end()){ //判断是否找到该元素
                //找到
                int res[] = {i, record[complement]};
                return vector<int>(res, res + 2);
            }

            record[nums[i]] = i;
        }

        throw invalid_argument("the input has no solution");  //为了严谨起见，如果没有解就会抛出异常
    }
};

问题7：3Sum

原题
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

/// Using two pointer technique
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        sort(nums.begin(), nums.end()); //先从小到大排序

        vector<vector<int>> res;  //记录结果数组

        int index = 0;   //记录一开始的位置
        while( index < nums.size() ){

            if( nums[index] > 0 )
                break;

            int bindex = index + 1;    //左边的指针
            int cindex = nums.size()-1;  //记录最右边的位置
            while( bindex < cindex) {    //左右两边还没遍历完

                if (nums[bindex] + nums[cindex] == -nums[index]) {
                    res.push_back({nums[index], nums[bindex], nums[cindex]});

                    // continue to look for other pairs
                    bindex = next_num_index( nums, bindex );   //
                    cindex = pre_num_index( nums, cindex);
                }
                else if (nums[bindex] + nums[cindex] < -nums[index])
                    bindex = next_num_index( nums, bindex );
                else //nums[bindex] + nums[cindex] > -nums[index]
                    cindex = pre_num_index( nums, cindex);
            }

            index = next_num_index( nums , index );
        }

        return res;
    }

private:
    int next_num_index( const vector<int> &nums, int cur ){

        for( int i = cur + 1; i < nums.size() ; i ++ )
            if( nums[i] != nums[cur] )
                return i;
        return nums.size();
    }

    int pre_num_index( const vector<int> &nums, int cur){

        for( int i = cur - 1; i >= 0 ; i -- )
            if( nums[i] != nums[cur] )
                return i;
        return -1;
    }
};

灵活选择键值

问题7：4Sum

原题
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.
Example:
Given array nums = [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]
]

/// Two pointers
/// Sort the array first.
/// For every different number a and b, try to find a pair (c, d), which a + b + c + d == 0
/// Using this way, we don't need to see whether the triplet is a repeated one
///
/// Time Complexity: O(nlogn) + O(n^3)
/// Space Complexity: O(1)
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> res;

        if(n < 4){
            return res;
        }

        sort(nums.begin(),nums.end());
        for (int i = 0; i <= n-4; i = nextNumberIndex(nums,i)) {
            for (int j = i+1; j <= n-3; j = nextNumberIndex(nums,j)) {
                int t = target - nums[i] - nums[j];

                if(nums[j+1] + nums[j+2] > t || nums[n-1] + nums[n-2] < t){
                    continue;
                }

                int p1 = j + 1;
                int p2 = nums.size() - 1;

                if (p1 >= p2)
                    break;

                while (p1 < p2){
                    if(nums[p1] + nums[p2] == t){
                        res.push_back({nums[i], nums[j], nums[p1], nums[p2]});

                        p1 = nextNumberIndex(nums, p1);
                        p2 = preNumberIndex(nums, p2);
                    } else if (nums[p1] + nums[p2] < t){
                        p1 = nextNumberIndex(nums, p1);
                    } else{
                        p2 = preNumberIndex(nums, p2);
                    }
                }


            }

        }

        return res;

    }

private:
    int nextNumberIndex( const vector<int> &nums , int index ){
        for (int i = index+ 1 ; i < nums.size(); i++) {
            if(nums[index] != nums[i]){
                return i;
            }
        }
        return nums.size();
    }

    int preNumberIndex( const vector<int> &nums , int index ){
        for (int i = index - 1; i >= 0; i--) {
            if(nums[index] != nums[i]){
                return i;
            }
        }
        return -1;
    }
};

解析：K-sums系列问题，采用定位法，确定边缘，往中间靠拢
1.排序，将头尾的数确定，利用下标记录当前的位置，若当前数大于0，表示3个数相加一定大于0，结束
2.若当前不是第1个数，判断和前面一个数是否重复
3.若当前3个数的和大于0，最高位往左移动；小于0，最低位往右移动；如等于0，
保存记录，并分别扫描左右两位是否重复

问题8：3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

/// Sorting + Two Pointers
/// Time Complexity: O(nlogn) + O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {

        assert(nums.size() >= 3);  //异常判断

        sort(nums.begin(), nums.end()); //从小到大排序

        int diff = abs(nums[0] + nums[1] + nums[2] - target);  //差值
        int res = nums[0] + nums[1] + nums[2];  //要返回的值

        for(int i = 0 ; i < nums.size() ; i ++){

            int l = i + 1, r = nums.size() - 1;
            int t = target - nums[i];//其他两个数的和（如果相等的话）
            while(l < r){
                if(nums[l] + nums[r] == t)
                    return nums[i] + nums[l] + nums[r];
                else{

                    if(abs(nums[l] + nums[r] - t) < diff){
                        diff = abs(nums[l] + nums[r] - t);
                        res = nums[i] + nums[l] + nums[r];
                    }

                    //继续遍历
                    if( nums[l] + nums[r] < t )
                        l ++;
                    else   // nums[l] + nums[r] > t
                        r --;
                }
            }
        }

        return res;
    }
};

问题9：4Sum II

原题
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2

/// Using Hash Map
/// Time Complexity: O(n^2)
/// Space Complexity: O(n^2)
class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {

        unordered_map<int,int> hashtable;   //有重复的元素，所以要用map，这里不需要用到顺序性，所以就用unordered_map
        for(int i = 0 ; i < C.size() ; i ++)
            for(int j = 0 ; j < D.size() ; j ++)
                hashtable[C[i]+D[j]] += 1;      //存储C[i]+D[j]的所有可能性

        int res = 0;  //结果
        for(int i = 0 ; i < A.size() ; i ++)
            for(int j = 0 ; j < B.size() ; j ++)
                if(hashtable.find(0 -A[i] - B[j]) != hashtable.end())  //查找到了
                    res += hashtable[-A[i]-B[j]];

        return res;
    }
};

问题10：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”]
]

解法一：

/// Using HashMap
/// Using characters frequency as key
///
/// Time Complexity: O(n*k) where k is the max length of string in strs
/// Space Complexity: O(n*k)
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;

        for ( const string& s : strs) {
            string key = getKey(s);
            map[key].push_back(s);
        }
        vector<vector<string>> res;
        for ( const auto& p : map) {
            res.push_back(p.second);
        }
        return res;
    }

private:
    //这一步可以合并
    string getKey(const string& s){
        vector<int> freq(26, 0);
        for ( char c : s ) {
            freq[c - 'a'] ++;   //算频率
        }
        string key = "";
        for ( int num : freq) {
            key += to_string(num) + "#";  //获取里面的字符串到key上
        }
        return key;
    }
};

解法二：优化

 
/// Using HashMap
/// Using sorted string as key
///
/// Time Complexity: O(n*klogk) where k is the max length of string in strs
/// Space Complexity: O(n*k)
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {

        unordered_map<string, vector<string>> map;
        for(const string& s: strs){//把容器里面的字符串抽取出来再排序
            string key = s;
            sort(key.begin(), key.end());
            map[key].push_back(s);
        }

        //返回结果集，要把结果集给回res容器
        vector<vector<string>> res;
        for(const auto& p: map)
            res.push_back(p.second);
        return res;
    }
};

问题11：Number of Boomerangs

原题
Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).Example:Input:
[[0,0],[1,0],[2,0]]
Output:
2

/// Using Hash Map
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {

        int res = 0; //记录结果
        for( int i = 0 ; i < points.size() ; i ++ ){

            // record中存储 点i 到所有其他点的距离出现的频次
            unordered_map<int, int> record;
            for(int j = 0 ; j < points.size() ; j ++)
                if(j != i)
                    // 计算距离时不进行开根运算, 以保证精度
                    record[dis(points[i], points[j])] += 1;

            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 vector<int> &pa, const vector<int> &pb){
        return (pa[0] - pb[0]) * (pa[0] - pb[0]) +
               (pa[1] - pb[1]) * (pa[1] - pb[1]);
    }
};

问题12：Number of Boomerangs(压轴题)

这个题暂时还不会做，等会做了再过来更新，呜呜呜~~~
哈哈哈 会做的小伙伴可以再评论区留言，一起来交流学习一下噢~

原题
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.Example 1:Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
±------------>
0 1 2 3 4
Example 2:Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
±------------------>
0 1 2 3 4 5 6

查找表和滑动窗口:

问题13：Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.Example 1:Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:Input: nums = [1,2,3,1,2,3], k = 2
Output: false

/// Using Hash Set
/// Time Complexity: O(n)
/// Space Complexity: O(k)
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {

        if(nums.size() <= 1)
            return false;

        if(k <= 0)
            return false;

        unordered_set<int> record;
        for(int i = 0 ; i < nums.size() ; i ++){

            if(record.find(nums[i]) != record.end())
                return true;

            record.insert(nums[i]);

            // 保持record中最多有k个元素
            // 因为在下一次循环中会添加一个新元素,使得总共考虑k+1个元素
            if(record.size() == k + 1)
                record.erase(nums[i - k]);
        }

        return false;
    }
};

问题13：Contains Duplicate

Given an array of integers, find if the array contains any duplicates.Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.Example 1:Input: [1,2,3,1]
Output: trueExample 2:Input: [1,2,3,4]
Output: falseExample 3:Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

/// Using HashTable
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {

        unordered_set<int> record;
        for( int i = 0 ; i < nums.size() ; i ++ )
            if( record.find( nums[i] ) == record.end() )
                record.insert( nums[i] );
            else
                return true;

        return false;
    }
};

二分搜索树底层实现的顺序性

原题
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolutedifference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.Example 1:Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

// Using Tree Set
// Time Complexity: O(nlogk)
// Space Complexity: O(k)
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

        if(t < 0)
            return false;

        set<long long> record;
        for(int i = 0 ; i < nums.size() ; i ++){
            //把绝对值的形式化简
            //lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
            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;
    }
};