LeetCode Permutation in String
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.
Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

class Solution {
public:
	bool checkInclusion(string s1, string s2) {
		int n = s1.size(), m = s2.size();
		if (n > m)return false;
		unordered_map<char, int> hash1;
		for (int i = 0; i < n; ++i)++hash1[s1[i]];
		for (int i = 0; i < m; ++i) {
			if (hash1.find(s2[i]) != hash1.end()) {
				if (i + n <= m) {
					unordered_map<char, int> hash2;
					for (int j = i; j < i + n; ++j)++hash2[s2[j]];
					if (hash1 == hash2)return true;
				}
			}
		}
		return false;
	}
};

本代码提交AC，用时1365MS。
优化方法是使用滑动窗口方法，假设s1的长度为n。先hash s1，再在s2中开长度为n的窗口，判断窗口内的子串hash是否和s1的hash相等，相等则返回tru，否则窗口向右滑动一格，即增加右边一个字符频率，同时减掉左边一个字符频率，如此循环。
代码如下：

class Solution {
public:
	bool checkInclusion(string s1, string s2) {
		int n = s1.size(), m = s2.size();
		if (n > m)return false;
		vector<int> hash1(26, 0), hash2(26, 0);
		for (int i = 0; i < n; ++i) {
			++hash1[s1[i] - 'a'];
			++hash2[s2[i] - 'a'];
		}
		if (hash1 == hash2)return true;
		for (int i = n; i < m; ++i) {
			++hash2[s2[i] - 'a'];
			--hash2[s2[i - n] - 'a'];
			if (hash1 == hash2)return true;
		}
		return false;
	}
};

本代码提交AC，用时13MS。

LeetCode 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 difference between i and j is at most k.

class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		if (nums.size() == 0)return false;
		unordered_map<int, int> hash_table;
		int distinct_cnt = 1; // 相异元素的个数
		vector<vector<int>> duplicate_indices = { {} }; // 跳过第0个桶
		for (int i = 0; i < nums.size(); i++) {
			if (hash_table[nums[i]] == 0) {
				hash_table[nums[i]] = distinct_cnt++;
				duplicate_indices.push_back({ i });
			}
			else {
				duplicate_indices[hash_table[nums[i]]].push_back(i); // 把相同元素的下标都放到一个桶里
			}
		}
		for (int i = 1; i < duplicate_indices.size(); i++) { // 查每个桶
			if (duplicate_indices[i].size() < 2)continue;
			for (int u = 0; u < duplicate_indices[i].size() - 1; u++) {
				for (int v = u + 1; v < duplicate_indices[i].size(); v++) {
					if (duplicate_indices[i][v] - duplicate_indices[i][u] <= k)return true;
				}
			}
		}
		return false;
	}
};

本代码提交AC，用时46MS。
后来看欣欣的解法LeetCode Contains Duplicate II，发现这个解法好厉害啊，用到了高级的unordered_set，之前只用过unordered_map，赶紧来学习一下。
她的思路是这样的，题目要求相同元素的距离不超过k，则我们维护一个长度为k的滑动窗口，把这个窗口里的所有数都hash到unordered_set里，后续每来一个元素，去这个hash_set里查之前是否出现过，因为我们的hash_set里只保留了前k个元素，所以如果hash_set查到了，他们的距离肯定是不超过k的。这种解法真是漂亮！完整代码如下：

class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		if (nums.size() == 0 || k <= 0)return false;
		if (k >= nums.size())k = nums.size() - 1;
		unordered_set<int> hash_set;
		for (int i = 0; i < nums.size(); i++) {
			if (i > k)hash_set.erase(nums[i - k - 1]); // 滑动窗口，删掉窗口第一个元素
			if (hash_set.find(nums[i]) != hash_set.end())return true;
			hash_set.insert(nums[i]); // 把新元素插入窗口
		}
		return false;
	}
};

本代码提交AC，用时29MS，果然比我的速度快，厉害~
二刷。用一个hash表记录每个数最近出现的下标，如果新来一个数，之前在hash表中出现过，则看看下标之差是否小于等于k，是则返回true；否则更新hash。
思路非常简单，代码如下：

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

本代码提交AC，用时35MS。