Two Sum
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. 求解
解法一
这个题最简单也是最容易的就是两层循环遍历，这个没什么可说的，时间复杂度为O(n^2)。
public class Solution {
public int[] twoSum(int[] nums, int target) {
int result[] = new int[2];
int n = nums.length;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
int sum = nums[i] + nums[j];
if(sum == target) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
}Leetcode Accepted，Runtime: 45 ms。
解法二
思考一下，如何进行优化呢？首先，条件为nums[i] + nums[j] = target，已知target和nums[i]的情况下，能不能直接确定nums[j]在数组中是否存在呢？这是可以的，很容易想到map结构，当然数据结构要变换一下，而map的查询复杂度为O(1)，map结构的设计有两种，要不是key为整数，要不key为整数的索引。由于我们求的是整数的索引，因此应该将key设为整数，value为整数的索引。但key为整数有一个问题就是，如果数组中存在相同整数，则后一个放入的数值会覆盖前一个，因此需要单独处理。题目中明确说了一个输入只有一个解，因此如果出现两个整数相等的情况，只需要找到另一个数字的索引即可。
public class Solution {
public int[] twoSum(int[] nums, int target) {
int result[] = new int[2];
int n = nums.length;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < n; i++) {
int other = target - nums[i];
map.put(nums[i], i);
if(map.containsKey(other)) {
//两个数字不等情况
if(other != nums[i]) {
//注意顺序
result[0] = map.get(other);
result[1] = i;
break;
}else {
//数字相等情况
result[0] = i;
for(int j = i + 1; j < n; j++) {
if(nums[j] == other) {
result[1] = j;
return result;
}
}
}
}
}
return result;
}
}Leetcode Accepted，Runtime: 12 ms。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年03月15日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录