Two Sum Java解决方案

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.

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

问题解读

这个问题使用Java是相对好解决的。

首先对问题进行解读，给出一个数组。如果数组中特定的两个数相加得到的数恰好为target，那么就以数组的形式返回这两个数的索引值。

结合例子，题目还提出每个样本都会有解答并且不会重复使用同一个元素。

本人使用了HashMap，其中Key代表数组中的每一个值，而Value代表对应的索引。

遍历数组并进行判断，如果map中的key恰好有数组中遍历到的值，就会停止遍历。

如果遍历到的nums[i]并不存在于map中，则对于数组这一项的值都用target值减去，并把(target-nums[i],i)存储到map中。

这里利用了这样思想，把(target-nums[i])作为key存储到map中，当遍历到的nums[j]与target-nums[j]恰好相等时，则说明存在两个数相加的值为target。

所以在匹配到停止遍历时，返回nums[i]在map中的索引值和遍历到的索引值i组合成的数组，即可。(这里可能需要自己思考举例)

Java代码

public int[] twoSum(int[] nums, int target) {

Map numMap = new HashMap<>();

int len = nums.length;

for(int i=0;i

if(numMap.containsKey(nums[i])){

int index = numMap.get(nums[i]);

return new int[]{index,i};

}else{

numMap.put(target-nums[i],i);

}

}

return new int[2];

}

运行复杂度

Runtime 2 ms

Memory 37.3 MB

Language java