Question:
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
Anwser 1: O(n*m)
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> ret(2, 0);
int len = numbers.size();
for(int i = 0; i < len; i++)
{
int tmp = target - numbers[i]; // another number
for(int j = i + 1; j < len; j++)
{
if(tmp == numbers[j])
{
ret[0] = i + 1; // +1 for not zero-based
ret[1] = j + 1;
return ret;
}
}
}
return ret;
}
};
Anwser 2: O(n*log(n))
typedef struct node{
int idx;
int val;
node(){};
node(int i, int v) : idx(i), val(v){}
}Node;
bool compare(const Node& a, const Node& b){
return a.val < b.val;
}
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len = numbers.size();
assert(len >= 2);
vector<int> ret(2, 0);
vector<Node> nums(len);
for(int i = 0; i < len; i++){
nums[i] = Node(i+1, numbers[i]);
}
sort(nums.begin(), nums.end(), compare); // O(n*log(n))
int l = 0;
int r = len - 1;
while(l < r){
int sum = nums[l].val + nums[r].val;
if(sum == target){
ret[0] = min(nums[l].idx, nums[r].idx); // val is compare, but idx not
ret[1] = max(nums[l].idx, nums[r].idx);
break;
} else if(sum < target){
l++;
} else {
r--;
}
}
return ret;
}
};
Anwser 3: O(n)
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len = numbers.size();
assert(len >= 2);
vector<int> ret(2, 0);
map<int, int> mapping; // default all are 0
vector<long long> mul(len, 0);
for(int i = 0; i < len; i++){
mul[i] = (target - numbers[i]) * numbers[i];
if(mapping[mul[i]] > 0){ // not default 0
if(numbers[i] + numbers[mapping[mul[i]] - 1] == target){
ret[0] = mapping[mul[i]];
ret[1] = i + 1;
break;
}
} else {
mapping[mul[i]] = i + 1; // larger than 0
}
}
return ret;
}
};
Anwser 4: O(n) in Java ( time is more longer and longer than C++)
public class Solution {
public int[] twoSum(int[] numbers, int target) {
// Start typing your Java solution below
// DO NOT write main() function
int len = numbers.length;
assert(len >= 2);
int[] ret = new int[2];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < len; i++){
if( !map.containsKey(numbers[i]) ){
map.put(target - numbers[i], i); // save another number
}
if( map.containsKey(numbers[i]) ){ // check is another number
int idx = map.get(numbers[i]);
if(idx < i){
ret[0] = idx + 1; // +1 for not zero-based
ret[1] = i + 1;
}
}
}
return ret;
}
}
参考推荐:
cplusplus_sort
Leetcode Questions
分享到:
相关推荐
Leetcode two sum java 解法
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
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)...
Leetcode 1 two sum C++ code
python python_leetcode面试题解之两数之和TwoSum
leetcode 2sum # Programming-Problems This will have many problems from all over the web, As of writing this readme there is Haskell 99: 28 finished + Huffman Coding LeetCode: LC1: 2Sum [Easy] LC2: Add...
TwoSum 如何贡献: 收录题库 LeetCode (还有4题未录入, 分别为 LRU Cache, Copy List with Random Pointer, Populating Next Right Pointers in Each Node I && II) PIE (未录入) CC150 (未录入) EPI (未录入) 每一个...
leetcode 答案 Leetcode Leetcode test 11 Container With Most Water 这里题目的分析图如下: 所以我们需要找的是ai,aj中的最小值作为高,然后找(i-j)的最大值作为长 ...twoSum ThreeSum FourSum...KSum
Two-Sum leetcode两数之和代码 题目描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组...
leetcode leetcode练习 twosum 问题 ;add two numbers问题;reverse integer问题;最大不重复子字符串长度问题;atoi问题;
这个方法实现的程序通过了LeetCode检测,提示用了16个测试,用时492ms,超过了75%的人
第一题的四种方法,包括暴力破解和字典、列表。我也是刚开始练习
leetcode-1-Two-Sum 这是我在 Github 的第一天。 我只是 AC leetcode 中的第一个问题。 从现在开始,我将使用Github在leetcode中记录我的生活。 我擅长 C++,但对 java 和 Python 不是很专业,我将使用最流行的 3 种...
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 ...
371 | [Sum of Two Integers](https://leetcode.com/problems/sum-of-two-integers/) | [C++](./C++/sum-of-two-integers.cpp) [Python](./Python/sum-of-two-integers.py) | _O(1)_ | _O(1)_ | Easy | LintCode | ...
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 ...
手绘算法力扣 1 两数之和(Two Sum)
题目 Twosum 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。...
Leetcode\TwoSum\TwoSum.cs 问题: 业绩报告: 反转整数 代码: Leetcode\ReverseInteger\ReverseInteger.cs 问题: 业绩报告: 回文数 代码: Leetcode\PalindromeNumber\PalindromeNumber.cs 问题: 从排序数组中...