本文将介绍【Leetcode】1.TwoSum的详细情况，特别是关于leetcode2sum的相关信息。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也将涉及一些关于1.Tw
本文将介绍【Leetcode】 1. Two Sum的详细情况，特别是关于leetcode 2 sum的相关信息。我们将通过案例分析、数据研究等多种方式，帮助您更全面地了解这个主题，同时也将涉及一些关于1. Two Sum - LeetCode、C++ leetcode::two sum、leetCode 1 Two Sum、LeetCode 1. Two Sum的知识。
本文目录一览：- 【Leetcode】 1. Two Sum（leetcode 2 sum）
- 1. Two Sum - LeetCode
- C++ leetcode::two sum
- leetCode 1 Two Sum
- LeetCode 1. Two Sum
【Leetcode】 1. Two Sum（leetcode 2 sum）
1. 英文题目
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 element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
2. 解题
public static int[] twoSum(int[] nums, int target) {
for (int i=0; i < nums.length; i++) {
for (int j=i+1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i,j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
1. Two Sum - LeetCode
Question
1. Two Sum
Solution
思路很简单这里就不说了，下面贴了不同的几个Java实现的时间与其他算法实现的时间的比较
这个是LeetCode的第一道题，也是我刷的第一道，刚一开始的Java实现
public int[] twoSum(int[] nums, int target) {
boolean find = false;
int targeti = -1, targetj = -1;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (i == j) {
continue;
}
if (nums[i] + nums[j] == target) {
targeti = i;
targetj = j;
find = true;
break;
}
}
if (find) {
break;
}
}
return new int[]{targeti, targetj};
}
稍微改进一下
public int[] twoSum(int[] nums, int target) {
boolean find = false;
int targeti = -1, targetj = -1;
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
targeti = i;
targetj = j;
find = true;
break;
}
}
if (find) {
break;
}
}
return new int[]{targeti, targetj};
}
下面这个版本是在讨论中看到的O(1)时间复杂度
public int[] twoSum3(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
result[1] = i;
result[0] = map.get(target - nums[i]);
return result;
}
map.put(nums[i], i);
}
return result;
}
C++ leetcode::two sum
上完C++的课就在也没用过C++了，最近要找实习，发现自己没有一门语言称得上是熟练，所以就重新开始学C++。记录自己从入门到放弃的过程，论C++如何逼死花季少女。
题目：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 element twice.
大意就是，给一个vector和target，在vector中找到两个数加起来等于target。
没仔细想就提交了自己的暴力解法。运行时间238ms，果真菜的不行，这个题最好的成绩是3ms。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
for(int i = 0; i != nums.size(); i++)
for(int j = i + 1; j!= nums.size(); j++)
if (nums[i] + nums[j] == target){
result.push_back(i);
result.push_back(j);
return result;
}
}
};
果断换一种解法，双指针法：将数组排序，用两个指针，i指向数组首元素，j指向数组尾元素，两个元素相加，大于target就j--，小于target就i--，找到正确的i、j之后，还要确定其在原数组中的下标，查找时要避免两个元素值相同时返回的下标也相同。例如：Input:[3,3] 6 ；Output:[0,0] ； Expected:[0,1]，提交之后运行时间为8ms
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
vector<int> sortednums(nums);
sort(sortednums.begin(),sortednums.end());
int i = 0, j = sortednums.size()-1;
while(i != j){
if (sortednums[i] + sortednums[j] > target)
j--;
else if (sortednums[i] + sortednums[j] < target)
i++;
else
{
vector<int>::iterator it =find(nums.begin(),nums.end(),sortednums[i]);
i = distance(nums.begin(),it);
nums[i] = nums[i] +1;
it = find(nums.begin(),nums.end(),sortednums[j]);
result.push_back(i);
result.push_back(distance(nums.begin(),it));
return result;
}
}
}
};class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
map<int,int> hashtable;
map<int,int>::iterator it;
for(int i = 0; i!= nums.size(); i++)
{
it = hashtable.find(target - nums[i]);
if (it != hashtable.end())
{
result.push_back(it->second);
result.push_back(i);
return result;
}
else if (!hashtable.count(nums[i]))
hashtable.insert(make_pair(nums[i], i));
}
}
};
static const auto __________ = []()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
using SizeType = remove_reference_t<decltype(nums)>::size_type;
using ValueToIndexMapType = unordered_map<int, SizeType>;
ValueToIndexMapType map;
vector<int> indices(2);
for (SizeType index = 0; index < nums.size(); ++index)
{
const auto foundIterator = map.find(target - nums[index]);
if (foundIterator != end(map) && foundIterator->second != index)
return vector<int>{ index, foundIterator->second };
else
map.emplace(nums[index], index);
}
throw std::runtime_error("Solution not found");
}
};
leetCode 1 Two Sum
https://leetcode.windliang.cc/ 第一时间发布
题目描述 （简单难度）
给定一个数组和一个目标和，从数组中找两个数字相加等于目标和，输出这两个数字的下标。
解法一
简单粗暴些，两重循环，遍历所有情况看相加是否等于目标和，如果符合直接输出。
public int[] twoSum1(int[] nums, int target) {
int []ans=new int[2];
for(int i=0;i<nums.length;i++){
for(int j=(i+1);j<nums.length;j++){
if(nums[i]+nums[j]==target){
ans[0]=i;
ans[1]=j;
return ans;
}
}
}
return ans;
}时间复杂度：两层 for 循环，O（n²）
空间复杂度：O（1）
解法二
在上边的解法中看下第二个 for 循环步骤。
for(int j=(i+1);j<nums.length;j++){
if(nums[i]+nums[j]==target){我们换个理解方式：
for(int j=(i+1);j<nums.length;j++){
sub=target-nums[i]
if(nums[j]==sub){第二层 for 循环无非是遍历所有的元素，看哪个元素等于 sub ，时间复杂度为 O（n）。
有没有一种方法，不用遍历就可以找到元素里有没有等于 sub 的？
hash table ！！！
我们可以把数组的每个元素保存为 hash 的 key，下标保存为 hash 的 value 。
这样只需判断 sub 在不在 hash 的 key 里就可以了，而此时的时间复杂度仅为 O（1）！
需要注意的地方是，还需判断找到的元素不是当前元素，因为题目里讲一个元素只能用一次。
public int[] twoSum2(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
int sub=target-nums[i];
if(map.containsKey(sub)&&map.get(sub)!=i){
return new int[]{i,map.get(sub)};
}
}
throw new IllegalArgumentException("No two sum solution");
}时间复杂度：比解法一少了一个 for 循环，降为 O（n）
空间复杂度：所谓的空间换时间，这里就能体现出来， 开辟了一个 hash table ，空间复杂度变为 O（n）
解法三
看解法二中，两个 for 循环，他们长的一样，我们当然可以把它合起来。复杂度上不会带来什么变化，变化仅仅是不需要判断是不是当前元素了，因为当前元素还没有添加进 hash 里。
public int[] twoSum3(int[] nums, int target) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int sub=target-nums[i];
if(map.containsKey(sub)){
return new int[]{i,map.get(sub)};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}总结
题目比较简单，毕竟暴力的方法也可以解决。唯一闪亮的点就是，时间复杂度从 O（n²）降为 O（n） 的时候，对 hash 的应用，有眼前一亮的感觉。
LeetCode 1. Two Sum
问题链接
LeetCode 1. Two Sum
题目解析
给定一数字数组及目标和，求数组中和为目标的两个数下标。
解题思路
暴力搜索肯定过不了，时间复杂度为 $O(n^2)$，TLE教你做人。
本题利用map可以轻松过，怎么用呢？简单理解为map可以在两个对象之间建立联系，即（key, value）。
数组中的数字作为map的key，对应数组索引值作为value。由于问题求解为 $x + y = target$，变个法子，$x = target - y$。遍历一遍数组，判断（target - nums[i]）是否出现过，由于题目说明只有一种解法，所以一旦判断通过，即可返回答案。时间复杂度为 $O(n)$。
小tip：注意这里一遍遍历时建立map数据，没有必要把所有数据加入map，也可以省去不少时间。
unordered_map 和 map 并无太大区别，C++11中的新容器，一个无序一个有序罢了，在不同情况下各有优势。这里只需要判断存在，所以选择无序的unordered_map即可。
unordered_map::count - C++ Reference
unordered_map::find - C++ Reference
参考代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
if (m.count(target - nums[i])) {
return {m[target - nums[i]], i};
}
m[nums[i]] = i;
}
return {};
}
};
相似题目
LeetCode 15. 3Sum
LeetCode 16. 3Sum Closest
LeetCode 18. 4Sum
LeetCode All in One题解汇总（持续更新中...）
本文版权归作者AlvinZH和博客园所有，欢迎转载和商用，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利.
我们今天的关于【Leetcode】 1. Two Sum和leetcode 2 sum的分享已经告一段落，感谢您的关注，如果您想了解更多关于1. Two Sum - LeetCode、C++ leetcode::two sum、leetCode 1 Two Sum、LeetCode 1. Two Sum的相关信息，请在本站查询。
本文标签：
![[转帖]Ubuntu 安装 Wine方法（ubuntu如何安装wine）](https://www.gvkun.com/zb_users/cache/thumbs/4c83df0e2303284d68480d1b1378581d-180-120-1.jpg)
