1. 两数之和
题面
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题解
暴力法
直接顺序双循环查找，O(n^2)
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
vector<int> result;
for(int i=0;i<nums.size()-1;++i)
{
for(int j=i+1;j<nums.size();++j)
{
if(nums[i]+nums[j]==target)
{
result.push_back(i);
result.push_back(j);
return result;
}
}
}
return result;
}
};
哈希表
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> a;
vector<int> b(2,-1);//结果
for(int i=0;i<nums.size();i++)
{
if(a.count(target-nums[i])>0)
{
b[0]=a[target-nums[i]];
b[1]=i;
break;
}
a[nums[i]]=i;//如果不存在与之匹配的数，则将其放入map中，用来获取结果下标
}
return b;
};
};
41. 缺失的第一个整数
题面
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
题解
如果可以使用线性级别的额外空间：
建立以键为索引的伪hash表，由于一共有n个数，据鸽笼原理，第一个缺失的正整数必然在1到n+1之间
使用双数组构成hash表，值数组初始化为全0
插入过程为T(n)
按键遍历hash表的值数组，如果键是1到n的整数，则修改值为1，遍历过程为T(n)
遍历值数组的第1到n个值，如果哪个值为0，则对应的键为第一个未出现，输出并返回，如果遍历完成后为全1，则由鸽笼原理，n+1为第一个未出现，输出并返回，解决过程为T(n)
//有一说一，这都从LeetCode上荡的题，各种方法都做过了
#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
//#include <algorithm>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::map;
using std::pair;
//int Key[1000000];
int Value[1000000] = { 0 };
int main()
{
vector<int> Key;
int n;
int temp;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> temp;
//Key[i] = temp;
Key.push_back(temp);
}
for (int i = 0; i < n; i++)
{
if (Key[i] > 0 && Key[i] <= n)
{
Value[Key[i]] = 1;
}
}
for (int i = 1; i <= n; i++)
{
if (Value[i] == 0)
{
cout << i;
return 0;
}
}
cout << n + 1;
return 0;
}
复杂度分析
O=T(N)+T(N)+T(N)=T(3N)
O(3N)->O(N)
空间复杂度为常数级（较大常数）
也可以优化为in place算法，遍历操作时进行前n个正整数向正确索引的换位即可，此时不需额外空间，线性空间占用
LCP 1. 猜数字
题面
小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？
输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。
示例 1:
输入：guess = [1,2,3], answer = [1,2,3]
输出：3
解释：小A 每次都猜对了。
示例 2:
输入：guess = [2,2,3], answer = [3,2,1]
输出：1
解释：小A 只猜对了第二次。
限制
1. guess的长度 = 3
2. answer的长度 = 3
3. guess的元素取值为 {1, 2, 3} 之一。
4. answer的元素取值为 {1, 2, 3} 之一。
我的题解
给新入门的小学生做的难度，bool运算可以取巧，没什么可说的
class Solution
{
public:
int game(vector<int>& guess, vector<int>& answer)
{
return ((guess[0]==answer[0])+(guess[1]==answer[1])+(guess[2]==answer[2]));
}
};
