Leetcode 刷题笔记
1.两数之和
题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
- 示例 1：
输入：nums = [2,7,11,15], target = 9， 输出：[0,1]
- 示例 2：
输入：nums = [3,2,4], target = 6， 输出：[1,2]
- 示例 3：
输入：nums = [3,3], target = 6， 输出：[0,1]
* 解法一
暴力法，二重循环
- 复杂度：暴力算法时间复杂度O（n²），空间复杂度O（1）。
* 解法二
排序+双指针
- 思想：用一个pair数组vec储存nums的内容（first）以及下标（second）。根据first中从小到大排序，最后利用双指针遍历数组进行匹配，返回对应的second中的内容，即数组下标。
- 复杂度：这里先将数组排序好O（nlogn），再利用双指针法遍历一遍O（n）得到结果。 为了保存下标信息另开了一个数组。时间复杂度O（nlogn），空间复杂度O（n）。
class Solution {
public:
static bool cmp(const pair<int,int>a,const pair<int,int>b){
return a.first<b.first;
}
vector<int> twoSum(vector<int>& nums, int target) {
vector<pair<int,int>> vec;
for(int i = 0; i < nums.size(); i++){
vec.push_back(make_pair(nums[i],i));
}
sort(vec.begin(),vec.end(),cmp);
int i = 0,j = nums.size()-1;
while(i<j){
if(vec[i].first+vec[j].first>target) {
j--;
}
else if(vec[i].first+vec[j].first<target) {
i++;
}
else if(vec[i].first+vec[j].first==target) {
return {vec[i].second,vec[j].second};
}
}
return {};
}
};
* 解法三
Hash表
- 思想：创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
- 复杂度：
- 时间复杂度：O(n)，其中 n 是数组中的元素数量。对于每一个元素 x，我们可以O(1)地寻找 target - x。
- 空间复杂度：O(n)，其中 n 是数组中的元素数量,主要为哈希表的开销。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
88.合并两个有序数组
题目： 给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。
注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
- 示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3。
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
- 示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0 。
输出：[1]。
解释：需要合并 [1] 和 [] 。合并结果是 [1] 。
- 示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1 。
输出：[1] 。
解释：需要合并的数组是 [] 和 [1] 。合并结果是 [1] 。注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
* 解法一
合并后直接排序
- 复杂度：
-
时间复杂度：O((m+n)log(m+n)) 排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)\log(m+n))
-
空间复杂度：O(log(m+n))。 排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(\log(m+n))O(log(m+n))。
-
* 解法二
双指针归并
- 复杂度：
-
时间复杂度：O(m+n)。 指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)。
-
空间复杂度：O(m+n)。 需要建立长度为 m+n 的中间数组 sorted。
-
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = 0, p2 = 0;
int sorted[m + n];
int cur;
while (p1 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
}
};
* 解法三
逆向双指针
- 算法思想： 通过题意所示，我们可以使用暴破，双指针+额外存储空间来完成该题，但是这两种做法的空间和时间复杂度至少都是 O(m + n) 。这个时候我们就要分析，为什么告诉我们 nums1.length >= m + n，很明显就能猜出出题者的意图，那就是考查原地修改，将空间复杂度降低到 O(1)。因为这样不需要使用额外的数组空间了，我们完全可以把 nums2 也放入 nums1 中。原地修改时，为了避免从前往后遍历导致原有数组元素被破坏掉，我们要选择从后往前遍历！所以，我们总共需要创建三个指针，两个指针用于指向 nums1 和 nums2 的初始化元素数量的末位，也就是分别指向 m-1 和 n-1 的位置，还有一个指针，我们指向 nums1 数组末位即可。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1;
int tail = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
cur = nums2[p2--];
} else if (p2 == -1) {
cur = nums1[p1--];
} else if (nums1[p1] > nums2[p2]) {
cur = nums1[p1--];
} else {
cur = nums2[p2--];
}
nums1[tail--] = cur;
}
}
};