TwoSum之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.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
创新互联凭借在网站建设、网站推广领域领先的技术能力和多年的行业经验,为客户提供超值的营销型网站建设服务,我们始终认为:好的营销型网站就是好的业务员。我们已成功为企业单位、个人等客户提供了成都网站制作、成都做网站服务,以良好的商业信誉,完善的服务及深厚的技术力量处于同行领先地位。
二、题目理解
给定一个整型数组以及一个目标值,求数组中两个相加等于目标值的元素的索引。此题假设给定的数组中一定有两个元素相加等于目标值。
三、实现代码
1、第一种实现方式
使用暴力搜索的方式,用双层for循环遍历数组,拿数组的每一个元素与其他元素相加之后与目标值进行对比,找出符合要求的两个元素。
实现代码如下:
public int[] twoSum01(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
break;
}
}
}
return result;
}
2、第二种实现方式
第一种实现方式在最坏的情况下的时间复杂度为O(n²),执行时间较长,不是一种比较好的实现方式,下面是第二种实现方法。
定义一个Map,遍历数组,每次都用目标值减去数组当前值得到差值temp,并判断temp是否存在于Map中,如不存在,则将数组当前值和索引存入Map中;如存在,则取出temp对应的索引值。
实现代码如下:
public int[] twoSum02(int[] nums, int target) {
HashMap tempMap = new HashMap();
int[] resultArr = new int[2];
for(int i = 0; i < nums.length; i++) {
// 用target减去数组当前值
int temp = target - nums[i];
// 判断HashMap中是否包含temp
if(tempMap.get(temp) != null) {
resultArr[0] = tempMap.get(temp);
resultArr[1] = i;
break;
} else {
tempMap.put(nums[i], i); // 如不包含,就将当前值存入Map中
}
}
return resultArr;
}
当前题目:TwoSum之Java实现
链接地址:http://pwwzsj.com/article/gsopse.html