leetcode 1. 两数之和

题目

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

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

示例:

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

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

解法1 暴力遍历

对于数组每一个元素x 遍历一遍数组，查找是否有 target - x元素存在

时间复杂度 O(n^2)

空间复杂度 O(1)

解法2 两次哈希表遍历

为了提高运行复杂度 我们需要引入哈希表来提高对于数组元素查询的效率，也就是常规思路“以空间换时间”

在第一次遍历中，我们建立长度为n的哈希表 ：key为 元素数值，value为元素下标索引。建立哈希表的时间复杂度为O(n)

第二次遍历中，我们对数组中每一个元素对应的target - x进行查询，如果找到，即返回当前元素索引以及哈希表访问到的元素对应下表的索引。查询的平均开销为O(1)

时间复杂度 O(n)

空间复杂度 O(n)

解法3 一次哈希表遍历

我们可以将建立哈希表和查询对应数值统筹到一次遍历中进行

对于数组中的每一个元素x，首先查询哈希表中有无对应的target - x元素 ,若存在，则可以返回结果，若不存在，则将对应的nums[i]-i键值对插入哈希表。

时间复杂度 O(n)

空间复杂度 O(n)

code:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map <int,int> array;
        unordered_map <int,int> ::const_iterator hm1;
        typedef pair<int,int> Int_Par;

        for(int i = 0; i < nums.size();i++)
        {
            hm1 = array.find(target - nums[i]);
            array.insert(Int_Par(nums[i],i));
            if(hm1 == array.end())
                continue;
            else {
                result.push_back(i);
                result.push_back(hm1->second);
                break;
            }
            
        }
        return result;
    }
};

Q&A

Q:当数组中出现重复元素，且重复元素正好为两数之和时，哈希表解法会不会产生冲突.

A:对于两次遍历哈希表解法，每次查询的时候需要验证target-num的解对应的value(索引）是否等于本身的索引。因为查询函数是优先返回较前键值对结果的，所以当以相对靠后的重复元素作为基准搜索时候，即可得到正确结果。

对于一次遍历哈希表，因为每次查询时，当前元素都未加入哈希表，所以不会出现这种问题。