twosum问题
1. 题目描述
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].
题目翻译:
给定一个整数数组,返回两个数的索引,这两个数的和要等于目标值。假定每一组输入只有一对数据满足条件(唯一性),同时不能使用同一个元素两次。
2. 解题思路
target的数值已经给出,在确定一个数的情况下在数组中找寻另外一个数,利用暴力解法就是两层循环进行扫描,满足条件立即返回,复杂度是O(N2)。这里能够简化的就是怎么来方便的寻找另外一个数值,因为一组数据中只有一对满足条件,这种唯一性可以利用map这种数据结构,因为map必须满足key值的唯一性。(这里存在问题是,输入的数组元素可以相同,leetcode对于这种情况没有说明,但是用例默认是包含相同情况的,利用map的唯一性对相同的数值进行了覆盖)。
利用<数值,索引>来构造map,只要有一组满足条件就可以返回。
3. 代码
- 双循环
public static int[] twoSum(int [] nums,int target) {
int[] result = new int[2];
HashMap<Integer,Integer> m = new HashMap<Integer,Integer>();
for(int i = 0;i < nums.length;i++){
m.put(nums[i], i);
}
for(int j = 0;j<nums.length;j++) {
int k = target - nums[j];
if(m.containsKey(k)&&m.get(k) != j) {
result[0] = j;
result[1] = m.get(k);
break;
}
}
return result;
}
- 单循环
public static int[] twoSum(int[] nums,int target) {
int[] result = new int[2];
HashMap<Integer,Integer> m = new HashMap<Integer,Integer>();
for(int i = 0;i<nums.length;i++) {
int k = target-nums[i];
if(m.containsKey(k)) {
result[0] = i;
result[1] = m.get(k);
break;
}
m.put(nums[i], i);
}
return result;
}
这里单循环就是利用了只有一组数据满足条件,同时因为map的性质,相同的元素只能允许存在一个,这里才能体现出怎么处理重复元素的问题。