原题链接:#1 Two Sum
要求:
给定一个整数数组,找出其中的两个数,使之相加能够得到目标数字。
函数twoSum应当返回这两个数的索引,index1应小于index2。请注意,这两个索引并非从零开始计数。
假定每个输入都有且只有一个解。
例:
输入:numbers{2, 7, 11, 15}, target=9
输出:index1=1, index2=2
难度:中等
分析:
对于这个问题,很直白的一个解是如方案1的一个双重循环。由于有且只有一个解,只要遍历时发现两个元素相加为目标值,便跳出循环并将这两个元素的索引返回即可。此方案最坏情况下的时间复杂度为O(n2)。
解决方案2使用一个HashMap作为辅助数据结构,建立倒排索引,将数组中的每个元素值作为key,该元素的索引作为值加入HashMap。然后遍历一次数组,对于数组中的每一项nums[i],当发现target-nums[i]也在HashMap的键集中,将对应项的索引返回即可。
方案2的唯一问题是原数组中可能有多个不同索引对应的值相同,此时加入HashMap时后加入的会将之前的值覆盖。故返回结果时需要注意这种情况,符合条件时将较小的索引值直接返回,而不是从反向索引中取值。
解决方案:
方案1:
public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; for(int i=1; i<=nums.length-1; i++){ for(int j=i+1; j<=nums.length;j++){ if(nums[i-1]+nums[j-1]==target){ result[0] = i; result[1] = j; break; } } } return result; }
方案2:
public int[] twoSum2(int[] nums, int target) { Map map = new HashMap<Integer, Integer>(); for(int i=0; i<nums.length; i++){ map.put(nums[i], i+1); } for(int i=1; i<=nums.length; i++){ if(map.containsKey(target-nums[i-1])&&((Integer)map.get(target-nums[i-1])>i)){ return new int[] {i, (Integer)map.get(target-nums[i-1])}; } } return new int[0]; }
相关推荐
leetcode 2 leetcode-训练 算法训练。 java $: javac hello.java java ...leetcode ...leetcode ...leetcode ...leetcode ...1.two-sum.cpp leetcode test 1.two-sum.cpp leetcode test 1.two-sum.cpp -t '[1,2,3]\n3'
leetcode 浇花力扣解决方案 简单的 #0001 - Two Sum #0007 - Reverse Integer #0009 - Palindrome Number #0035 - Search Insert Position #0058 - Length of Last Word #0066 - Plus One #0083 - Remove Duplicates...
twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的答案(index1 和 index2)不是从零开始的。 您可以假设每个输入都只有一个解决方案。 输入:number={2, 7, 11, ...
leetcode 答案LeetCode LeetCode in Swift 这个Repo 用来存下我在LeetCode 解题的原始档,包含解题中遇到的错误,也包含解出AC 的答案, 以下的清单将连结到我的Github Pages 中,皆有题目中文翻译与解题的过程。...
_001_TwoSum | | | | |-- twoSum.java | | | | |-- twoSum.kt | | | | |-- twoSum.md | |-- ...... 非常欢迎讨论和代码审查。 TwoSum.java在 Java 中提供了 OJ 接受的解决方案。 TwoSum.kt在 Kotlin 中提供 OJ 接受...
leetcode 不会二和整数数组 给定一个整数数组,返回两个数字的索引,使它们相加为特定目标。 您可以假设每个输入都只有一个解决方案,并且您不能两次使用相同的元素。 例子: Given nums = [2, 7, 11, 15], target =...
two_sum 16 二总和 17 BFS 18 two_pointers, two_sum 19 滑动窗口 20 堆 21 , 22 回溯 23 24 26 27 28 , kmp, dfa 31 33 binary_search 34 35 36 37 38 39 , 40 , 42 44 45 贪婪的 46 47 48 49 50 51 , 52 , 53 贪婪...
leetcode 2 和 c 二和 我的 LeetCode C 代码解决方案:二和 Success Details Runtime: 4 ms, faster than 97.08% of C online submissions for Two Sum. Memory Usage: 5.8 MB, less than 99.36% of C online ...
Two-Sum 要点: - 利用java中Array对象的sort方法排序,使得整个数组呈升序状态 - 再利用两段取点相加的sum与target比较 - 若大于target,则后结点前移,sum变小 - 若小于target,则前结点后移,sum变大...
leetcode 答案 LeetCode笔记- 1.ArrayPartition数组划分: ...2.TwoSum两数之和: 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
1-1 BinarySearch 1-2 即使简单的问题,也有很多优化的思路 283 27 26 80 1-3 三路快排partition思路的应用 Sort Color 75 88 215 1-4 对撞指针 Two Sum II - Input Array is Sorted 167 125 344 345 11 1-5 滑动...
leetcode 答案 LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于...
判断链表是否为回文链表 leetcode leetCode-Exercise 个人 LeetCode 练习合集。 目前需要使用的数据结构 题解 Two Sum ...array ...nums[1] ...1] ...twoSum(_ target: Int, elements: [Int]) -> [Int] { var
文件名:E_001_TwoSum 源文件示例: /** * [1] Two Sum * * difficulty: Easy * * TestCase Example: [2,7,11,15] 9 * * https://leetcode-cn.com/problems/two-sum/ * * * Given an array of integers, return
191 |[Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/) | [C++](./C++/number-of-1-bits.cpp) [Python](./Python/number-of-1-bits.py) | _O(1)_ | _O(1)_ | Easy ||| 201 | [Bitwise AND of ...
leetcode 1004 leetcode E:简单,M:中等,H:困难 数组和字符串 217. Contains Duplicate (E) 48. Rotate Image (M) -> 2 73. Set Matrix Zeroes (M) 1. Two Sum (E) 167. Two Sum II - Input array is sorted (E)...
twoSum(int[] nums, int target) { Map m=new HashMap();//注意哈希表初始化时,Map<>中必须是Object,不能用简单数据类型; int tem; for(int i=0;i<nums.length;++i){ tem=target-nums[i]; if(m.containsKey...
leetcode 答案力码 参考文献 问题:容易 问题·选ぶにあたり、参考になりそうなサイト 蟒の文法解说 问题 src/answer/two_sum.py src/answer/two_sum_2.py src/answer/two_sum_4.py src/answer/running_sum_of_1d_...
nums[i-1]: (#15. 3Sum) if idx > start and nums[idx] == nums[idx-1]: continue (#40. Combination Sum II) Tip5: 鸽笼原理要记得,如果题目说要constant extra space,八成就是用input array + swap(#41. First ...
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2)...