两数之和

四月 14, 2018

LeetCode

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v;
        map<int, int> m;
        
        //暴力法
        // for(int i = 0; i < nums.size(); i ++)
        // {
        //     std::cout << nums[i] << endl;
        //     cout << target << endl;
        //     for(int j = i + 1; j < nums.size(); j ++)
        //     {
        //         if(nums[j] == target - nums[i])
        //         {
        //             v.push_back(i);
        //             v.push_back(j);
        //             break;
        //         }
        //     }
        // }

        //一遍哈希表
        for(int i = 0; i < nums.size(); i++)
        {
            int value = target - nums[i];
            if(m.find(value) != m.end())
            {
                v.push_back(m.find(value)->second);
                v.push_back(i);
                break;
            }
            m.insert(map<int, int>::value_type(nums[i], i));
        }
        return v;
    }
};

第一种暴力法：

遍历每个元素，并且查找是否存在一个值与target-nums[i]相等的目标元素。

时间复杂度：

$O(n^2)$

空间复杂度：

$O(1)$

第二种一遍哈希表：

在进行迭代并将元素插入到表中之前，我们会先检查表中是否已经存在当前元素所对应的目标元素。如果存在，那么我们已经找到了对应的解，并立即将其返回。

时间复杂度：

$O(n)$

我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。

空间复杂度:

$O(n)$

所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。
images

查看评论