题目

题解

1. 暴力法

就是挨个两两相加，找到相加为target的两个数。会超时，比较好写，这里不写了

  • 时间复杂度$O(n^{2})$
  • 空间复杂度$O(1)$

2. 两遍哈希表

哈希表的key为当前值，value为当前值在数组中的下标值
两次遍历，第一次存值进入哈希表，第二次在哈希表中找target减去该值

class Solution {//用散列表，两次遍历，时间O(n)
public:
    vector<int> twoSum(vector<int>& nums, int target) {//
        unordered_map<int,int> m;//设置散列表m
        vector<int> output;//设置输出数组
        for(int i=0;i<nums.size();++i)//第一次循环
        //设置散列表，键值为数组中的值，值为下标值
            m[nums[i]]=i;
        for(int i=0;i<nums.size();++i){//第二次循环
            int t = target - nums[i];//设置t为目标值-当前值
            if(m.count(t) && m[t] != i){//在散列表里找t
                output.push_back(i);
                output.push_back(m[t]);//找到之后把这两个下标存到output中
                break;//跳出循环
            }
                
        }
        return output;
    }
};

3. 一遍哈希表

哈希表的key为当前值，value为当前值在数组中的下标值
遍历一遍数组，边存值边找target减去该值的下标

class Solution {//用散列表，一次遍历，时间O(n)
public:
    vector<int> twoSum(vector<int>& nums, int target) {//
        unordered_map<int,int> m;//设置散列表m
        vector<int> output;//设置输出数组
        for(int i=0;i<nums.size();++i){//一次循环
            int t = target - nums[i];//设置t为目标值-当前值
            if(m.count(t) && m[t] != i){//在散列表里找t,因为不能用同样元素所以m[t] != i
                output.push_back(i);
                output.push_back(m[t]);//找到之后把这两个下标存到output中
                break;//跳出循环
            }
        m[nums[i]]=i;
        //查找完之后再将值加入散列表，即对每个值先查是否有前面的值与该值的和为target
                
        }
        return output;
    }
};