两数之和（Leetcode）

题目：

解法一：暴力法

        int n=nums.size();
        vector<int> ans;
        for(int i=0;i<n;++i)//从头到尾遍历数组
        {
            for(int j=i+1;j<n;++j)//从i的下一个位置开始查找，满足题目输出顺序的要求
            {
                if(nums[i]+nums[j]==target)
                {
                    ans.push_back(i);
                    ans.push_back(j);
                }
            }
        }
        return ans;
    }

最坏的情况是全部元素都需要遍历一遍，因此时间复杂度为O(N^2); 空间使用为常量级别，因此空间复杂度为O(1).

解法二：哈希法

        vector<int> ans;
        unordered_map<int,int> m;//C++11新特性加入的容器，底层为无序哈希表
        for(int i=0;i<nums.size();++i)
        {
            if(m.find(target-nums[i])!=m.end())//find函数如果失败返回为容器末尾迭代器
            {
                ans.push_back(m[target-nums[i]]);
                ans.push_back(i);
            }
            m[nums[i]]=i;
        }
        return ans;
    }

由于使用了哈希表查找，最差的情况是将N个元素放入到哈希表中，然后查找出来的时间只需要O(1),这个函数的时间复杂度为N*O(1)，即O(N)；

由于哈希表的使用，存入了N个元素，因此空间复杂度为O(N)；