当前位置 博文首页 > 复古风的博客：七 .（未做：164） LeetCode标签刷题——数组（一
给定一个整数数组
nums和一个整数目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。数据保证有且仅有一组解。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
这个题目保证一定有解，且只有一个答案。
c++中map的底层实现原理是平衡树，插入删除操作时间复杂度是O(logn);
而unordered_map的底层实现原理是哈希表，插入删除操作时间复杂度是O(1);
map说明参考
代码：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> heap; //定义一个c++哈希表，第一个int代表数值，第二个代表下标，即完成数值到下标的映射。
for(int i=0;i<nums.size();i++){ //从数组第一个数开始遍历第二个数，
int r=target-nums[i]; //令r=target-第二个数数值，即r代表的是我们需要的第1个数的数值。
if(heap.count(r))return{heap[r],i}; //heap.count(r)代表如果数组中所需的第一个数的数量不空，即存在第一个数，我们就返回heap[r],即代表r数值对应的下标；i代表第二个数的下标。
else heap[nums[i]]=i; //否则我们就把这个数插入到哈希表中，nums[i]代表数值，heap[nums[i]]=i即把nums[i]对应的下标映射到i。
}
return {}; //如果不存在就返回空，其实没必要写，但是力扣题目不写就会有警告。
}
};
2021年8月14日21:34:10：
//把数组中的数放到哈希表中，我们枚举第二个数，当扫描到Si的时候，前面的S0,S1...Si-1均已经存在于哈希表中了，我们访问Si的时候，
//我们看一下哈希表中是否有target-Si这个数，如果存在，就找到了答案，否则就把Si放到哈希表中，哈希表中记录的是数值与位置的对应关系
//注意哈希表中记录的就是数组中数值与其下标位置的对应，注意题目已经保证了只存在一组答案，所以不会存在两个相同的数使得后一个把前一个数的位置顶替的情况
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>(); //记录数组中的数值与其下标位置的对应关系
for(int i=0;i<nums.length;i++){
int a=target-nums[i]; //a是要寻找的前一个数
if(map.containsKey(a)){
return new int[]{i,map.get(a)}; //返回答案
}else{
map.put(nums[i],i); //否则就把当前数加到哈希表中
}
}
return new int[]{}; //返回空数组的情况
}
}
给定两个大小为
m和n的正序（从小到大）数组 nums1和nums2。请你找出并返回这两个正序数组的中位数。进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int tot=nums1.size()+nums2.size(); //记录两个数组的总长度；注意.size()时间复杂度是O(1)
if(tot%2==0){ //如果总长度为偶数，
int left=find(nums1,0,nums2,0,tot/2); //寻找中间偏左数，
int right=find(nums1,0,nums2,0,tot/2+1); //寻找中间偏右数，
return (left+right)/2.0; //注意要除以2.0，因为结果让我们求的是带小数的结果；
}else return find(nums1,0,nums2,0,tot/2+1); //如果总长度是奇数，返回中间的数即可。
}
int find(vector<int>& nums1,int i,vector<int>& nums2,int j,int k){
if(nums1.size()-i>nums2.size()-j) return find(nums2,j,nums1,i,k); //如果递归过程中，第一个数组的大小大于了第二个数组的大小，就交换两个数组的地位；
if(k==1){ //如果递归过程中，两个数组只剩下了一个元素，
if(nums1.size()==i) return nums2[j]; //如果短数组元素为空就j返回第二个数组元素
else return min(nums1[i],nums2[j]); //否则返回两个数组的最小值。
}
if(nums1.size()==i) return nums2[j+k-1]; //如果递归过程中，短数组元素已空就返回长数组的第k个元素，
int si=min((int)nums1.size(),i+k/2),sj=j+k-k/2; //定义两个指针。
if(nums1[si-1]>nums2[sj-1]) return find(nums1,i,nums2,sj,k-(sj-j)); //看图，如果数组1的第k/2的元素大于数组2的第k/2个元素，就把数组2的前k/2个元素删除。
else return find(nums1,si,nums2,j,k-(si-i)); //看图，如果数组1的第k/2的元素小于或者等于数组2的第k/2个元素，就把数组1的前k/2个元素删除。
}
};
二刷第四题：
class
