内容简介:给定一个整数数组你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。<!--more-->
题目描述
给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
<!--more-->
我的垃圾思路
One
- 我能想到的只有一个循环去遍历每个数字,一个循环去匹配是否有符合的 -- O(n^2)
- 首先想到暴力破解,两个for循环去找哪两个索引对应的值加起来等于
target
(当然这估计过不了关) - 但是想到了
HashMap
有个get
方法效率很高,那么首先把数组中所有元素put
到map
中,将target - nums[i]
作为key,索引index
作为value
,那么再写一个循环去遍历数组时候,判断起来就很方便了。 - 直接用
map.get(nums[i])
,即可拿到对应的value
,当value
不为null
的时候证明满足了nums[i] + nums[j] = target
,也就是nums[i] = target - nums[j]
。如上面示例的话,map中会存放的是map:{7:0, 2:1, -2:2, -6:3}
- 然后再写一个循环去判断
int b = map.get(nums[i])
不为空 且b != i
时<font color=grey size=2>(因为当nums[0]==3
,target==6
就会得到[0,0],很显然这是错误的,题目中提到了不能重复利用这个数组中同样的元素)</font>,即可break
,[i,b]
就是答案
Two
- 不过还是写个两个循环,能否写成一个循环呢?(根据提交的答案结果看来,两者差距不大)
- 那就是一个循环,边循环,边
put
到map
中(key,value
同上),循环过程中再去判断是否map
已经contains
这个nums[i]
了,如果包含则满足了nums[i] = target - nums[j]
,即可以break
上面都将 $ O(n^2)->O(n) $
我的垃圾代码
package com.dasnnj.practice.simple; import java.util.Arrays; import java.util.HashMap; import java.util.Map; /** * Description <p> TODO: * 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 * 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 * <p> * 示例: * <p> * 给定 nums = [2, 7, 11, 15], target = 9 * <p> * 因为 nums[0] + nums[1] = 2 + 7 = 9 * 所以返回 [0, 1]</p> * * @author DASNNJ <a href="mailto:dasnnj@outlook.com"> dasnnj@outlook.com </a> * @date 2019-04-28 15:38 */ public class TwoSum { static int[] twoSum(int[] nums, int target) { //One /*//key为target-nums[i],value为index Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(target-nums[i],i); } int[] res = new int[2]; for (int i = 0; i < nums.length; i++) { Integer b; if ((b = map.get(nums[i])) != null && b != i) { res[0] = b; res[1] = i; break; } } return res; */ //Two //key为target-nums[i],value为index Map<Integer, Integer> map = new HashMap<>(); int[] res = new int[2]; for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { res[0] = map.get(nums[i]); res[1] = i; break; } map.put(target - nums[i], i); } return res; } public static void main(String[] args) { int[] nums = new int[]{2, 7, 11, 15}; System.out.println(Arrays.toString(TwoSum.twoSum(nums, 9))); } }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- 算法题:两数之和
- Leetcode 1:两数之和
- LeetCode题解 - 1. 两数之和
- LeetCode 第 1 号问题:两数之和
- LeetCode 1:两数之和 Two Sum
- LeetCode算法系列_0891_子序列宽度之和
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。