Given an array of integers, find two numbers such that they add up to a specific target number.
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) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
可以用一个暴力的方式,用嵌套的FOR循环 O(N^2)
for(int i = 0;i<numbers.length;i++){
for(int j = i;j<numbers.length;j++){
if(numbers[i]+numbers[j]==target&&i != j){
return new int[]{i+1,j+1};
}
}
}
return null;
但是这个没有用,时间太长了不通过。
可以不用这种时间复杂度高的,可以自己定义一个类,来进行运算。但是更取巧的一个方法是可以通过hashmap进行一个解决,具体代码如下
int [] result = new int[2];
HashMap<Integer,Integer> a = new HashMap<Integer,Integer>();
for(int i = 0;i<numbers.length;i++){
if(a.get(target - numbers[i])!= null){
result[0] = i+1<a.get(target - numbers[i])?i+1:a.get(target - numbers[i]);
result[1] = i+1>a.get(target - numbers[i])?i+1:a.get(target - numbers[i]);
}else{
a.put(numbers[i], i+1);
}
}
return result;
时间复杂度为O(nLOGn),是基本的牺牲空间来提升效率的方式。
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) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
可以用一个暴力的方式,用嵌套的FOR循环 O(N^2)
for(int i = 0;i<numbers.length;i++){
for(int j = i;j<numbers.length;j++){
if(numbers[i]+numbers[j]==target&&i != j){
return new int[]{i+1,j+1};
}
}
}
return null;
但是这个没有用,时间太长了不通过。
可以不用这种时间复杂度高的,可以自己定义一个类,来进行运算。但是更取巧的一个方法是可以通过hashmap进行一个解决,具体代码如下
int [] result = new int[2];
HashMap<Integer,Integer> a = new HashMap<Integer,Integer>();
for(int i = 0;i<numbers.length;i++){
if(a.get(target - numbers[i])!= null){
result[0] = i+1<a.get(target - numbers[i])?i+1:a.get(target - numbers[i]);
result[1] = i+1>a.get(target - numbers[i])?i+1:a.get(target - numbers[i]);
}else{
a.put(numbers[i], i+1);
}
}
return result;
时间复杂度为O(nLOGn),是基本的牺牲空间来提升效率的方式。
发表评论
-
Merge k Sorted Lists
2015-03-12 19:55 327Merge k sorted linked lists and ... -
Generate Parentheses
2015-03-12 19:50 365Given n pairs of parentheses, w ... -
Generate Parentheses
2015-03-05 22:39 0Given n pairs of parentheses, w ... -
Valid Parentheses
2015-03-05 22:33 309Given a string containing just ... -
Remove Nth Node From End of List
2015-03-05 22:31 340Given a linked list, remove the ... -
Letter Combinations of a Phone Number
2015-03-05 22:30 332Letter Combinations of a Phone ... -
4Sum
2015-03-05 22:26 312Given an array S of n integers, ... -
3Sum Closest
2015-03-05 22:25 292Given an array S of n integers, ... -
3Sum
2015-03-03 22:34 319Given an array S of n integers, ... -
Longest Common Prefix
2015-03-03 22:21 328Write a function to find the lo ... -
Roman to Integer
2015-03-03 22:20 328Given a roman numeral, convert ... -
Integer to Roman
2015-03-01 23:35 289Given an integer, convert it to ... -
Container With Most Water
2015-03-01 22:55 323Given n non-negative integers a ... -
Regular Expression Matching
2015-03-01 20:19 367Implement regular expression ma ... -
Palindrome Number
2015-02-13 22:08 332Determine whether an integer is ... -
String to Integer (atoi)
2015-02-13 11:07 343Implement atoi to convert a str ... -
Reverse Integer
2015-02-12 23:39 227Reverse digits of an integer. ... -
ZigZag Conversion
2015-02-12 23:37 255The string "PAYPALISHIRING ... -
Longest Palindromic Substring
2015-02-12 22:50 334Given a string S, find the long ... -
Add Two Numbers
2015-02-12 22:12 300You are given two linked lists ...
相关推荐
Two Sum算法调试小demo
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)...
本文给大家介绍的是C++实现two sum问题的暴力算法,蛮力解法意味着我们需要检查每一个数字与后面是否可以组成target,在数字量不大的情况下还是可以得到很好的效果,所以蛮力法的字符串匹配仍然是得到了实际生活中的...
twoSum0.zip
Leetcode 1 two sum C++ code
Leetcode two sum java 解法
twoSum问题的核心思想.md
手绘算法力扣 1 两数之和(Two Sum)
python python_leetcode面试题解之两数之和TwoSum
题目 Twosum 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。...
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
js代码-1. Two Sum
leetcode leetcode练习 twosum 问题 ;add two numbers问题;reverse integer问题;最大不重复子字符串长度问题;atoi问题;
14 Two Sum II Input array is sorted 49 15 Two Sum III Data structure design 51 16 3Sum 53 17 4Sum 55 18 3Sum Closest 57 19 String to Integer (atoi) 59 20 Merge Sorted Array 61 ... ... 231 Counting ...
1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to ...
leetcode-1-Two-Sum 这是我在 Github 的第一天。 我只是 AC leetcode 中的第一个问题。 从现在开始,我将使用Github在leetcode中记录我的生活。 我擅长 C++,但对 java 和 Python 不是很专业,我将使用最流行的 3 种...
Two Sum. Memory Usage: 5.8 MB, less than 99.36% of C online submissions for Two Sum. #1. Two Sum Given an array of integers nums and an integer target, return indices of the two numbers such that they...
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 ...
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 ...