LC1两数之和

LC1两数之和

方法一、暴力 O(n^2)

var twoSum = function(nums, target) { 
            let res = [];     for (let i = 0; i < nums.length; i  ) { 
                for (let j = i   1; j < nums.length; j  ) { 
                    if (nums[i]   nums[j] == target) { 
                        res.push(i,j);             }         }     }     return res; }; 

方法二：

循环遍历数组nums，在每个循环中做以下两件事

1. 判断target - nums[i]是哈希表吗？
2. 将nums[i]插入哈希表

题目保证，只有一组解决 只需扫描一次，哈希表插入和删除操作的复杂性是O(1) 因此，时间复杂度为O(n)

var twoSum = function(nums, target) { 
            let map = new Map();     for (let i = 0; i < nums.length; i  ) { 
                let n2 = target - nums[i];         if(map.has(n2)) { 
       
            return [map.get(n2),i];
        } else { 
       
            map.set(nums[i],i);
        }
    }
    return 0;
};