1. 两数之和（hashmap）
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
解题思路：以数组的值为map的key，以数组下标为map的值
知识点：unordered_map的使用
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> umap;
// 遍历当前元素，并在umap中寻找是否有匹配的key
for(int i = 0;i < nums.size();i++){
auto match = umap.find(target-nums[i]);
if(match!=umap.end())
return {match->second, i};
// 如果未找到匹配，就把访问过的元素和下标添加到umap中
umap[nums[i]] = i;
}
return {};
}
};136. 只出现一次的数字（异或运算）
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
解题思路：异或运算
知识点：
- 任何数与 0 异或的结果是它本身，即 a ^ 0 = a。
- 任何数与自身异或的结果是 0，即 a ^ a = 0。
- 异或运算满足交换律和结合律，即 a ^ b ^ a = b ^ a ^ a = b ^ (a ^ a) = b ^ 0 = b。
因此，如果我们将数组中所有元素进行异或运算，相同的元素都会变成 0，最后剩下的结果就是只出现一次的元素。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for(int i = 0;i<nums.size();i++){
ans ^= nums[i];
}
return ans;
}
};169. 多数元素（计数器）
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解题思路：map计数，大于len/2即为答案
知识点：unordered_map作计数器
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int> map;
int ans = 0;
int len = nums.size();
for(int i = 0;i < len;i++){
map[nums[i]]++;
if(map[nums[i]] > len/2){
ans = nums[i];
break;
}
}
return ans;
}
};75. 颜色分类（原地排序）
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。
解题思路：每次遍历调整一个数的位置，第一次让0全到前边去，第二次是1，这样2就自然到了后面
class Solution {
public:
void sortColors(vector<int>& nums) {
int n = nums.size();
int ptr = 0;
for(int i = 0;i < n;i++){
if(nums[i]==0){
swap(nums[i],nums[ptr]);
ptr++;
}
}
for(int i = ptr;i < n;i++){
if(nums[i]==1){
swap(nums[i],nums[ptr]);
ptr++;
}
}
return;
}
};35. 搜索插入位置（经典二分）
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。
知识点：二分查找
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left = 0;
int right = n - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效
int middle = left + ((right - left) >> 1);// 防止溢出 等同于(left + right)/2
if (nums[middle] > target) {
right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
// 当目标值等于数组中某一个元素 直接return middle;
return middle;
}
}
// 还需处理如下三种情况
// 目标值在数组所有元素之前 [0, -1]
// 目标值插入数组中的位置 [left, right]，return right + 1
// 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以return right+1
return right + 1;
}
};27. 移除元素（快慢指针）
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
知识点
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
定义快慢指针
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int fast = 0, slow = 0;
for(;fast<nums.size();fast++){
if(nums[fast]!=val){
nums[slow++] = nums[fast];
}
}
return slow;
}
};
Comments NOTHING