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
求目标整数的两个加数,并返回其下标(C++下标+1)。
题目不难,值得注意的就是上面黄字的地方。因为可以利用这个条件稍微优化一点,使得循环由n^2编程n^2/2。循环少一半。
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> twoIndices;
if(numbers.empty()) return twoIndices;
for(int i=0; i<numbers.size(); i++)
{
int temp = target - numbers[i];
twoIndices.push_back(i+1);
for(int k=i+1; k<numbers.size(); k++)
{
if(temp == numbers[k])
{
twoIndices.push_back(k+1);
return twoIndices;
}
}
twoIndices.pop_back();
}
return twoIndices;
}
};
本题目leetcode上已经更新,由之前的10个testcase变成15个testcase了,可见leetcode还是在不断更新的。
更新之后,上面的程序就会超时了,所以我也更新一下程序,这次使用hash表,复杂度降低为O(n),或者说接近O(n).
vector<int> twoSum(vector<int> &numbers, int target)
{
unordered_map<int, int> mp;
vector<int> rs(2);
for (int i = 0; i < numbers.size(); i++)
{
int left = target - numbers[i];
if (mp.count(left))
{
rs[0] = mp[left]+1;
rs[1] = i+1;
return rs;
}
mp[numbers[i]] = i;
}
return rs;
}
分享到:
相关推荐
Leetcode two sum java 解法
python python_leetcode面试题解之两数之和TwoSum
leetcode两数之和代码 题目描述:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个...
答案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)...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 来源:力扣...
js代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 ...
手绘算法力扣 1 两数之和(Two Sum)
Leetcode 1 two sum C++ code
java代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
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...
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 | ...
leetcode-1-Two-Sum 这是我在 Github 的第一天。 我只是 AC leetcode 中的第一个问题。 从现在开始,我将使用Github在leetcode中记录我的生活。 我擅长 C++,但对 java 和 Python 不是很专业,我将使用最流行的 3 种...
设计并实现一个 TwoSum 的类,使该类需要支持 add 和 find 的操作。find 操作 - 寻找内部数据结构中是否存在一对整数,使得两数之和与给定的数
两数之和 array,hash 2 Add Two Numbers 两数相加 math 3 Longest Substring Without Repeating Characters 无重复字符的最长子串 string 4 LMedian of Two Sorted Arrays 两个排序数组的中位数 ary,binary search,...
leetcode 和 oj 二和 编写一个函数,该函数接受一组数字(用于测试的整数)和一个目标数字。 它应该在数组中找到两个不同的项目,当它们相加时,给出目标值。...基于:twoSum [1, 2, 3] 4 === (0, 2)
第四章 Leetcode 题解 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 ...
swift代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
一.个人探索 二.网上优秀编程 三....一....1.暴力解法 答题思路:两个循环来遍历列表中的所有组合可能... def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)) : for j in range(i+1