两数之和~

题目

思路和算法

暴力枚举数组中每一个数x，寻找数组中是否存在target-x
c++:

class Solution {
public:
    vector twoSum(vector& nums, int target) {
            for(int i= 0; i 
java:
 
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
                for(int j=i+1; j 
复杂度分析
 
时间复杂度：O(n^2),其中n是数组中的元素数量，最坏情况下数组中的任意两个数都要被匹配一下
空间复杂度O(1).
 
方法二：哈希 
思路和算法
 
注意方法一中查找target-x的复杂度过高，因此我们可以用哈希表存储值和下标的对应关系，将复杂度降为O(1)
 
c++:
 
class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_map m;
    for (int i = 0; i < nums.size(); i++)
    {
        m[target - nums[i]] = i + 1;
    }
    for (int i = 0; i < nums.size(); i++)
    {
        if (m[nums[i]]&& (i != m[nums[i]] - 1))
        {
            return {i, m[nums[i]] - 1};
        }
    }
    return {};
    }
};
 
java
 
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map hashMap = new HashMap();
        for(int i=0; i 
复杂度分析
 
时间复杂度：O(n),其中n是数组中的元素数量,对于每一个x，我们可以O(1)的寻找target-x
空间复杂度O(1)