BM50 两数之和
简单 通过率：37.01% 时间限制：1秒 空间限制：256M
知识点数组哈希
描述
给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
数据范围：2≤len(numbers)≤105，−10≤numbersi≤109，0≤target≤109
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)
示例1
输入：
[3,2,4],6
返回值：
[2,3]
说明：
因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2,3]
示例2
输入：
[20,70,110,150],90
返回值：
[1,2]
说明：
20+70=90
我们能想到最直观的解法，可能就是两层遍历，将数组所有的二元组合枚举一遍，看看是否是和为目标值，但是这样太费时间了，既然加法这么复杂，我们是不是可以尝试一下减法：对于数组中出现的一个数a，如果目标值减去a的值已经出现过了，那这不就是我们要找的一对元组吗？这种时候，快速找到已经出现过的某个值，可以考虑使用哈希表快速检验某个元素是否出现过这一功能。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res;
//创建哈希表，key是值、value是下标
unordered_map<int, int> m;
//在哈希表中查找target-numbers[i]
for(int i = 0; i < numbers.size(); i++){
int temp = target - numbers[i];
//若是没找到，将此信息计入哈希表
if (m.find(temp) == m.end()) {
m[numbers[i]] = i;
} else {
//哈希表中记录的是之前的数字，之前的数字的索引比当前数字小
res.push_back(m[temp] + 1);
res.push_back(i + 1);
break;
}
}
return res;
}
};
BM54 三数之和
中等 通过率：24.88% 时间限制：1秒 空间限制：256M
知识点数组双指针排序
描述
给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。
数据范围：0≤n≤1000，数组中各个元素值满足 ∣val∣≤100
空间复杂度：O(n2)，时间复杂度 O(n2)
注意：
三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
解集中不能包含重复的三元组。
例如，给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10)
示例1
输入：
[0]
返回值：
[]
示例2
输入：
[-2,0,1,1,2]
返回值：
[[-2,0,2],[-2,1,1]]
示例3
输入：
[-10,0,10,20,-10,-40]
返回值：
[[-10,-10,20],[-10,0,10]]
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
vector<vector<int> > res;
//int n = num.size();
if(num.size() < 3) {
return res;
}
sort(num.begin(), num.end());
for(int i = 0; i < num.size() - 2; i++){
if(i != 0 && num[i] == num[i - 1]) {
continue;
}
//区间起始下标
int left = i + 1;
int right = num.size() - 1;
//设置当前数的负值为目标
int target = -num[i];
while (left < right) {
if (num[left] + num[right] == target) {
//双指针指向的二值相加为目标，则可以与num[i]组成0
res.push_back({num[i], num[left], num[right]});
while (left + 1 < right && num[left] == num[left + 1]) {
//去重
left++;
}
while (right - 1 > left && num[right] == num[right - 1]){
//去重
right--;
}
//双指针向中间收缩
left++;
right--;
} else if(num[left] + num[right] > target) {
//双指针指向的二值相加大于目标，右指针向左
right--;
} else {
//双指针指向的二值相加小于目标，左指针向右
left++;
}
}
}
return res;
}
};
BM53 缺失的第一个正整数
题目
题解(110)
讨论(100)
排行
面经new
中等 通过率：39.17% 时间限制：1秒 空间限制：256M
知识点
数组
哈希
描述
给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数
进阶： 空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
数据范围:
-2^{31}\le nums[i] \le 2^{31}-1−2
31
≤nums[i]≤2
31
−1
0\le len(nums)\le5*10^50≤len(nums)≤5∗10
5
示例1
输入：
[1,0,2]
复制
返回值：
3
复制
示例2
输入：
[-2,3,4,1,5]
复制
返回值：
2
复制
示例3
输入：
[4,5,6,8,9]
复制
返回值：
1
复制
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int minNumberDisappeared(vector<int>& nums) {
unordered_set<int> s;
for (int i = 0; i < nums.size(); ++i) {
s.insert(nums[i]);
}
int num = 1;
while (s.find(num) != s.end()) {
num++;
}
return num;
}
};
JZ39 数组中出现次数超过一半的数字
简单 通过率：33.06% 时间限制：1秒 空间限制：256M
知识点哈希数组
描述
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
数据范围：n≤50000，数组中元素的值 0≤val≤10000
要求：空间复杂度：O(1)，时间复杂度 O(n)
输入描述：
保证数组输入非空，且保证有解
示例1
输入：
[1,2,3,2,2,2,5,4,2]
返回值：
2
示例2
输入：
[3,3,3,3,2,2,2]
返回值：
3
示例3
输入：
[1]
返回值：
1
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
//无序哈希表统计每个数字出现的次数
unordered_map<int, int> m;
//遍历数组
for(int i = 0; i < numbers.size(); i++){
//哈希表中相应数字个数加1
m[numbers[i]]++;
//一旦有个数大于长度一半的情况即可返回
if(m[numbers[i]] > numbers.size() / 2)
return numbers[i];
}
return 0;
}
};
BM52 数组中只出现一次的两个数字
题目
题解(184)
讨论(205)
排行
面经new
中等 通过率：55.22% 时间限制：1秒 空间限制：256M
知识点
位运算
哈希
描述
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
数据范围：数组长度 2\le n \le 10002≤n≤1000，数组中每个数的大小 0 < val \le 10000000<val≤1000000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
提示：输出时按非降序排列。
示例1
输入：
[1,4,1,6]
复制
返回值：
[4,6]
复制
说明：
返回的结果中较小的数排在前面
示例2
输入：
[1,2,3,3,2,9]
复制
返回值：
[1,9]
复制
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindNumsAppearOnce(vector<int>& array) {
unordered_map<int, int> m;
vector<int> res;
for (int i = 0; i < array.size(); ++i) {
m[array[i]]++;
}
for (int i = 0; i < array.size(); ++i) {
if (m[array[i]] == 1) {
res.push_back(array[i]);
}
}
sort(res.begin(), res.end());
return res;
}
};