【LeetCode】第一题：两数之和

题目

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

给定 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> twoSum;
        for (int i = 0; i < nums.size(); i++){
            for (int j = i + 1; j < nums.size(); j++){
                if (nums[j] + nums[i] == target){
                    twoSum.push_back(i);
                    twoSum.push_back(j);
                    return twoSum;
                }
            }
        }
    }
};

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range (i+1, len(nums)):
                if(nums[i] + nums[j] == target):
                    rtype = [i,j]
                    return rtype

个人提交结果为暴力法，遍历每个元素 xx，并查找是否存在一个值与 target - x 相等的目标元素。

复杂度分析：

• 时间复杂度：O(n^2)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n^2)。

• 空间复杂度：O(1)。 

官方题解 - 一遍哈希表

事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

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

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashdic = {}
        for i,num in enumerate(nums):
            tmp = target - num
            for key, value in hashdic.items():
                if value == tmp:
                    return [key,i]
            hashdic[i] = num
        return None

复杂度分析：

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

• 空间复杂度：O(n)O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 nn个元素。

 

本文地址：https://blog.csdn.net/jiiiiiaaaa/article/details/85983304