两数之和 (简单)
题目描述
给定一个整数数组和一个目标值, 找出数组中和为目标值的两个数; 你可以假设每个输入只对应一种答案, 且同样的元素不能被重复利用.
例如: 给定 nums = [2,7,11,15] ,target = 9 因为 nums[0] + nums[1] = 9; 因此返回 [0,1];
v1.0 代码如下: 正数, 0 或重复值通过测试; 异常用例: [-1, -2, -3, -4, -5] -8; 输出 []
- /**
- * @param {number[]} nums
- * @param {number} target
- * @return {number[]}
- */
- var twoSum = function(nums, target) {
- var tmp = target;
- var result = [];
- for(i=0; i <nums.length; i++){
- if(nums[i] <= tmp){
- tmp = target - nums[i];
- var last = nums.length - i - 1;
- for(j=0; j < nums.length; j++){
- if(nums[j] === tmp && j != i){
- result.push(i,j);
- return result;
- }
- }
- }
- }
- return result;
- };
分析: 首先想到使用减法得到另一个数, 因此考虑过滤掉所有小于 target 的值; 但未考虑负数的情况. 解决方案, 去掉外循环的 if 判断
官方解析:
上述方案属于暴力解法, 遍历每个元素并查找是否有一个值与 target-x 相等的元素. 时间复杂度 O(n2); 空间复杂度 O(1);
方法 2 两遍哈希表
为了优化时间复杂度, 需要更有效的方法来检查数组中是否存在目标元素. 如果存在, 需要知道其索引. 保持数组中每个元素与其索引相互对应的最好方法是哈希表.
通过以空间换取速度的方式, 我们可以将查找时间从 O(n)降低到 O(1). 哈希表正是为此目的而构建的, 它支持以 近似 恒定的时间进行快速查找. 我用 "近似" 来描述, 是因为一旦出现冲突, 查找用时可能会退化到 O(n). 但只要你仔细地挑选哈希函数, 在哈希表中进行查找的用时应当被摊销为 O(1).
算法思路: 使用两次迭代. 在第一次迭代中, 将每个元素的值和其索引添加到表中, 在第二次迭代中, 检查每个元素所对应的目标元素 (target - nums[i]) 是否存在于表中. 同时注意该元素不能是该元素本身.
- Code:
- /**
- * 在 js 中没有 hashTable, 但是 js 的 Object 属性是基于
- * hashTable 实现的, 因此可以有:
- * var person = {};
- * person['name'] = "Test"
- * 因此, 利用该特性, 封装 hashTable 的函数即可使用
- **/
- var twoSum = function(nums, target){
- var result = [];
- for(i=0; i < nums.length; i++>){
- map.add(nums[i], i);
- }
- for(i=0; i < nums.length; i++){
- var tmp = target - nums[i];
- if(map.containsKey(tmp) && map.getValue(tmp) != i){
- result.push(i);
- result.push(map.getValue(tmp));
- }
- }
- }
- var map = new HashTable();
- var HashTable = function(){
- // HashTable 一般操作包括:
- // add(k, v); getValue(k); remove(k);
- // containsValue(v); containsKey(k);
- // getValues(); getSize(); getKeys();
- // Clear();
- var size = 0;
- var entry = new Object();
- this.add = function(k, v){
- if(!this.containsKey(k)){
- size++;
- entry[k] = v;
- }
- }
- this.getValue = function(k){
- return this.containsKey(k) ? entry[k] : null;
- }
- this.remove = function(k){
- if(this.containsKey(k) && delete entry[k]{
- size--;
- }
- }
- this.containsKey = function(k){
- return (k in entry);
- }
- this.containsValue = function(v){
- for (var prop in entry){
- if(entry[prop] == value){
- return true;
- }
- }
- return false;
- }
- this.getValues = function(){
- var values = new Array();
- for(var prop in entry){
- values.push(entry[prop]);
- }
- return values;
- }
- this.getKeys = function(){
- var keys = new Array();
- for(var prop in entry){
- keys.push(prop);
- }
- return keys;
- }
- this.getSize = function(){
- return size;
- }
- this.clear = function(){
- size = 0;
- entry = new Object();
- }
- }
在上述方法中, 时间复杂度为 O(n); 哈希表的引入使得查找元素的时间缩短到 O(1); 空间复杂度为 O(n);
代码为 js 编写, 因此在方案 2 中需要自行实现一个 Hash Table
来源: http://www.bubuko.com/infodetail-2647697.html