1. 题目描述:
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
Level | AC rate |
Easy | 52.8% |
1. 题目解析:
给出了两种做法,一种是暴力求解,遍历两遍数组,当遍历得到两数之和为目标值就输出,第二种是哈希表存储,遍历一遍数组,一边遍历一边存储,代码如下:
// 暴力求解
class Solution {
public int[] twoSum(int[] nums, int target) {
int length = nums.length;
int[] num = new int [2];
int i,j;
for(i=0;i<length-1;i++)
{
for(j=i+1;j<length;j++)
{
if((nums[i]+nums[j])==target)
{
num[0] = i;
num[1] = j;
return num;
}
}
}
return num;
}
}
// 哈希表存储-java
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i<nums.length; i++){
if(map.isEmpty())map.put(nums[i],i);
else{
if(map.containsKey(target-nums[i]))
return new int[] {map.get(target-nums[i]),i};
else map.put(nums[i],i);
}
}
return new int[] {0,0};
}
}
执行用时:2 ms, 在所有 Java 提交中击败了72.76%的用户
内存消耗:41.7 MB, 在所有 Java 提交中击败了40.67%的用户
// 哈希表存储-cpp
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> nc;
for(int i = 0; i<nums.size() ; i++){
if(nc.empty())nc.insert(pair<int,int>(nums[i],i));
else{
if(nc.count(target-nums[i]))return vector<int>{nc[target-nums[i]],i};
else nc.insert(pair<int,int>(nums[i],i));
}
}
return vector<int>{0,0};
}
};
执行用时:16 ms, 在所有 C++ 提交中击败了47.82%的用户
内存消耗:10.9 MB, 在所有 C++ 提交中击败了13.78%的用户
88. 题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
Level | AC rate |
Easy | 52.4% |
88. 题目解析:
见之前的文章:
第88题 合并两个有序数组题目描述:给你两个按 非递减顺序 排列的整数数组 nums1和 nums2,另有两个整数 m 和 n ,分别https://mp.weixin.qq.com/s?__biz=Mzk0MjM5ODM2NQ==&mid=2247483673&idx=1&sn=a7577213b7da8a4da9eb5a31f350aa9a&chksm=c2c28febf5b506fd264457c166e0412de9b082c346441168c52c2dc0027e10ad7b10af933f95&scene=21#wechat_redirect这里之所以再写一遍是为了复习和练习一下cpp的语法,准备转cpp了。代码如下:
// CPP
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for(int pos1 = m-1, pos2 = n-1, pos = m+n-1; pos>=0; pos--){
if(pos1==-1){
nums1[pos] = nums2[pos2--];
continue;
}
if(pos2==-1){
nums1[pos] = nums1[pos1--];
continue;
}
if(nums1[pos1]>nums2[pos2]){
nums1[pos] = nums1[pos1--];
}
else{
nums1[pos] = nums2[pos2--];
}
}
return;
}
};
执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:8.7 MB, 在所有 C++ 提交中击败了66.11%的用户
// java
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m-1;
int p2 = n-1;
int p = m+n-1;
while(p1 >= 0 && p2 >= 0){
nums1[p--] = nums1[p1]>nums2[p2]?nums1[p1--]:nums2[p2--];
}
if(p2 >= 0){
System.arraycopy(nums2,0,nums1,0,p2+1);
}
}
}
执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:41.5 MB, 在所有 Java 提交中击败了46.91%的用户