一，两数之和
1. 两数之和 - 力扣（LeetCode）
https://leetcode.cn/problems/two-sum/
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { } };
1，暴力枚举：
如果找到两数之和，返回两数下标。
如果没找到，返回空。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for (int i = 0; i < nums.size()-1; i++) { for (int j = i + 1; j < nums.size(); j++) { if (nums[i] + nums[j] == target) { return { i,j }; } } } return {}; } };
复杂度分析
时间复杂度：O(N ^2 )，其中 NN 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
空间复杂度：O(1)
2，哈希表
思路及算法
注意到方法一的时间复杂度较高的原因是寻找target 一x的时间复杂度过高。因此,我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。使用哈希表，可以将寻找target 一x的时间复杂度降低到从O(N)降低到0(1)。这样我们创建一个哈希表， 对于每一个x，我们首先查询哈希表中是否存在target 一x,然后将x插入到哈希表中， 即可保证不会让x和自己匹配。
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 {}; } };
复杂度分析
时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以O(1) 地寻找 target - x。
空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。
二，合并两个有序数组
88. 合并两个有序数组 - 力扣（LeetCode）
https://leetcode.cn/problems/merge-sorted-array/
1，
最直观的方法是先将数组nums2放进数组 nums 1 的尾部，然后直接对整个数组进行排序。
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for (int i = 0; i != n; ++i) { nums1[m + i] = nums2[i]; } sort(nums1.begin(), nums1.end()); } };
复杂度分析
●时间复杂度: 0((m + n)log(m + n))。
排序序列长度为m + n,套用快速排序的时间复杂度即可，平均情况为0(m + n)log(m + n))
●空间复杂度: O(log(m + n))。
排序序列长度为m + n,套用快速排序的空间复杂度即可，平均情况为O(log(m + n))。
2，双指针
算法
方法一没有利用数组nums 1 与 nums 2已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示：
我们为两个数组分别设置一个指针p1 与p2 来作为队列的头部指针。代码实现如下：
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)。
指针移动单调递增，最多移动m + n次,因此时间复杂度为O(m + n)。
●空间复杂度: O(m + n)。
需要建立长度为m + n的中间数组sorted。
3，逆向双指针
算法
方法二中，之所以要使用临时鼂,是因为如果直接合并到数组nums1中，nums1 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖nums1中的元素呢?观察可知，nums1 的后半部分是空的,可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进nums1的最后面。
严格来说，在此遍历过程中的任意一个时刻， nums1 数组中有m- p1 - 1个元素被放入nums1的后半部, .nums2数组中有n- p2- 1个元愫被放入nums1的后半部，而在指针p1的后面，nums1 数组有m+n-p1-1个位置。由于
m+n-P1-1≥m-P1一1+n-P2一1
等价于
P2≥-1
永远成立，因此p1后面的位置永远足够容纳被插入的元素，不会产生p1的元素被覆盖的情况。
实现代码如下:
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; } } };
复杂度分析
●时间复杂度: O(m + n)。
指针移动单调递减，最多移动m + n次,因此时间复杂度为O(m + n)。
●空间复杂度: O(1)。
直接对数组nums1原地修改，不需要额外空间。
以上部分来自本人在力扣的整理。
