# 哈希表-LeetCode 217、219、220、232（hashset、hashmap）

【LeetCode #217】存在重复元素

(哈希表)

```class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> set;
for(auto num: nums){
if(set.count(num)){
return true;
}else{
set.insert(num);
}
}
return false;
}
};```

(排序法)

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

【LeetCode #219】存在重复元素II

```class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> hashmap;
for(int i = 0; i < nums.size(); i++){
if(hashmap.count(nums[i])){
if(i - hashmap[nums[i]] <= k){     //判断相同的值得索引差值
return true;
}else{
hashmap[nums[i]] = i;  //更新nums[i]的索引
}
}else{
hashmap.emplace(nums[i], i);
}
}
return false;
}
};```

【LeetCode #220】存在重复元素III

```class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if(k < 1 || t < 0){
return false;
}
int size = nums.size();
if(size == 1)  return false;

set<long long> s;
int low = 0;
for(int i = 0; i < size; i++){
auto it = s.lower_bound((long long)nums[i]-t);
if(it != s.end() && *it <= (long long)nums[i]+t){
return true;
}
s.insert(nums[i]);     // 使得滑动窗口的大小不变
if(s.size() == k+1){
s.erase(nums[low++]);
}
}
return false;
}
};```

【LeetCode #232】用栈实现队列

```class MyQueue {
public:
/** Initialize your data structure here. */
stack<int> data;
stack<int> tmp;
MyQueue() {}

/** Push element x to the back of queue. */
void push(int x) {
data.push(x);
}

/** Removes the element from in front of queue and returns that element. */
int pop() {
if(tmp.empty()){
int size = data.size();
while(size--){
tmp.push(data.top());
data.pop();
}
}
int t = tmp.top();
tmp.pop();
return t;
}

/** Get the front element. */
int peek() {
if(tmp.empty()){
int size = data.size();
while(size--){
tmp.push(data.top());
data.pop();
}
}
return tmp.top();
}

/** Returns whether the queue is empty. */
bool empty() {
return data.empty() && tmp.empty();
}
};

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/```

0 条评论

• ### 最大堆，DP问题-LeetCode 373 374 376 377 605（DP，最大堆）

给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums...

• ### gcd，哈希问题-LeetCode 357、355、365、367、380

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。

• ### 单调栈-LeetCode 739、287（单调栈，桶计数）

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定...

• ### 剑指Offer题解

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少存在一个数字是重复的。 请找出数组中任意一个重复的数字，但不能修改输入的数组。 例如输...

• ### 查找数组中两数之和等于指定的数

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

• ### 【LeetCode】136. Single Number

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 【LeetCode】两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

• ### Largest Number Greater Than Twice of Others

思路1： 非排序，如果存在一个数，比其他任何数的两倍还大必然是最大数。时间复杂度为O(n2)O(n^2)