leetcode 1 Two Sum Java & JavaScript解法

2018-03-01 11:14:13来源:segmentfault作者:soleil阿璐人点击

分享
题目详情
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

题目的意思是,输入一个整数数组和一个目标和,让我们找整数数组中的两个元素,使他们的加和刚好等于目标和。返回这两个元素的位置。每个输入都有且仅有一组满足条件的元素。


Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].



想法如果使用蛮力法可以简单的解决这个问题。但是需要两层循环,效率低。
所以我们新声明一个hashmap用来存储中间结果,使得只需要一趟遍历就可以完成查找。
HashMap remain用来存储,每一个元素和目标元素的差值和这个元素的位置。这样的话,如果我们后续遍历到的元素刚好等于这个差值,就说明这两个元素加和刚好等于目标和。
所以对于每次遍历到的元素num,先查找remain中有没有key和num相等,如果有,则返回这两个元素的位置,如果没有,就把target-num的值和num的位置放入hashmap。解法
public int[] twoSum(int[] nums, int target) {
int[] res= {-1,-1};
HashMap<Integer,Integer> remain = new HashMap<Integer,Integer>();for(int i=0;i<nums.length;i++){
if(remain.containsKey(nums[i])){
res[0] = remain.get(nums[i]);
res[1] = i;
return res;
}else{
remain.put(target-nums[i], i);
}
}return res;
}
javaScript篇
方法一
蛮力法~两层循环暴力解决~
var twoSum = function(nums, target) {
var res = new Array;
for(let i=0;i<nums.length-1;i++){
let temp = target - nums[i];
for(let j = i+1;j<nums.length;j++){
if(temp == nums[j]){
res[0] = i;
res[1] = j;
return res;
}
}
}
};
方法二
因为javascript没有hashmap这种数据结构,所以我们这里用对象来代替map。因为js里的对象也是key-value键值对。
var twoSum = function(nums, target) {
var ans = [];
var exist = {};for (var i = 0; i < nums.length; i++){
if (typeof(exist[target-nums[i]]) !== 'undefined'){
ans.push(exist[target-nums[i]]);
ans.push(i);
}
exist[nums[i]] = i;
}return ans;};

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台