本文共 2160 字,大约阅读时间需要 7 分钟。
文章作者:Tyan
博客: | |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].
解法一
这个题最简单也是最容易的就是两层循环遍历,这个没什么可说的,时间复杂度为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; Mapmap = new HashMap (); 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。
转载地址:http://vdwui.baihongyu.com/