leetcode1:两数之和

1. 题意

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

2. 思路

1. 首先肯定是暴力解法双重循环暴力解决，复杂度 O（n2）
2. 如果题目是有序的话我们可以二分优化一重循环，不是有序可以用map记录下标但这样也不是很好
3. 我们可以借鉴桶排序思想用map记录一下，前面出现的值，循环寻找，这样就优化了一重循环，用空间复杂度换时间复杂度

3.代码展示

1.暴力解法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int d = nums.size();
        vector<int> result;
        int flag = 0;
        for(int i = 0; i < d; i++){
            for(int j = 0; j < d; j++){
                if(i == j) continue;
                if(nums[i] + nums[j] == target && i != j){
                    result.push_back(i);
                    result.push_back(j);
                    flag = 1;
                    break;
                }
            }
            if(flag) break;
        }
        return result;
    }
};

map优化解法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mp;
        int n = nums.size();
        for(int i = 0; i < n; i++)
        {
            if(mp.count(target - nums[i]))
                return {mp[target -nums[i]], i};
            mp[nums[i]] = i;
        }
        return {-1, -1};
    }
};

4.总结

1.好久没打比赛了有点生疏，呜呜呜我哭
2.leetcode这oj形式真难用
3.博客终于搭好了，开始写点技术类博客