第1题 两数之和+第88题合并两个有序数组

1. 题目描述：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

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 。

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%的用户