Long

欢迎来到Long的博客站点

第1题: two_sum

题目描述

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法一

本解法暴力破解,直接两次遍历数组,求出满足条件的结果,时间复杂度是o(n ^ 2)

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

};

这里直接暴力破解,但是在时间上花费太久,把代码放在leetcode中运行,也有点汗颜,在第一次做这道题目的时候,由于我算法思想实在薄弱,所以只想到了这种解法,同时,对于别人的解法也看不懂,但是我告诉自己,我只是刚开始,算法这东西是需要积累的,所以本着慢慢来的态度,这次再一次刷这道题目,立刻明白了。

解法二

这里利用了map的结构特性,在map中查找一个元素的时间是o(logN),如果是undered_map,时间复杂度是o(1),所以利用undered_map来,所以总的时间复杂度是o(n),立刻优化了好多。这里说一下思路,利用undered_map数据结构,该结构的底层实现是hash,所以查找一个元素的时间复杂度是O(1),由于需要往该结构(设该结构名为index_val)中放入数据,这时需要遍历整个数组,所以整个算法的时间复杂度是O(n),建立hash结构时,key为数组中的元素,这时可以直接查找符合条件的值(target – nums[i]),因为找到之后需要返回这两个元素的下标,所以,hash结构中的value是元素的下标值。

class Solution 
{
public:
    Solution() {}

    vector<int> twoSum(vector<int> & nums, int target) 
    {
        if (nums.size() <= 1)
        {
            return vector<int>();
        }

        //建立索引和值的hash_map结构
        unordered_map<int, int> index_val;
        //map<int, int> index_val;
        for (int i = 0; i < nums.size(); ++i)
        {
            index_val.insert(std::make_pair(nums[i], i));
        }

        for (int i = 0; i < nums.size(); ++i)
        {
            auto iter = index_val.find(target - nums[i]);
            if (iter != index_val.end() && iter->second != i)
            {
                vector<int> vec{i, iter->second};
                return vec;
            }
        }
    }
};

上面的算法不难理解,其实就是利用了target和hash结构查找元素的时间复杂度非常低,这里可以看见hash结构的优势以及别样的用法。从上面的代码中可以知道,我们是提前建立好了hash,往hash结构中插入了数据,这时是否可以考虑优化代码,不需要等hash结构完全建立好,在建立hash_map的同时查找我们需要的元素是否在hash_map中,如果在则直接返回;如果不在则继续建立hash_map结构,最后总会找到满足条件的下标。

class Solution 
{
public:
    Solution() {}

    vector<int> twoSum(vector<int> & nums, int target) 
    {
        if (nums.size() <= 1)
        {
            return vector<int>();
        }

        //建立索引和值的hash_map结构
        unordered_map<int, int> index_val;
        //map<int, int> index_val;
        for (int i = 0; i < nums.size(); ++i)
        {
            auto iter = index_val.find(target - nums[i]);
            if (iter != index_val.end())
            {
                vector<int> vec{i, iter->second};
                return vec;
            }
            index_val.insert(std::make_pair(nums[i], i));
        }
    }
};

从上面的代码可以看出来,解法二中的两份代码进行比较会发现,在循环中的if条件判断中,最后一份代码没有判断 iter->second != i, 这是因为我们在当前i下标的元素建立hash_map之前进行查找的,查找目标元素是否在我们当前已经建立好的hash_map中;这时我们是不会重复利用数组的元素的,所以不需要该判断条件。该代码表示,不管怎么样,如果存在符合条件的元素,最后是总能找到的。

点赞

发表评论

电子邮件地址不会被公开。