## leetcode-two sum 原

梦想游戏人

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.

Example:

```Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].```

``````
class Solution1 {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
static int cache[99999] = { -1 };//缓存数字 该数字可能重复值

for (int i = 0; i < 99999; i++)
{
cache[i] = -1;
}
static vector<int> cache1[99999];//缓存该数字的index

for (int i = 0; i < nums.size(); i++)
{
cache[i] = nums[i];
int index = nums[i];
auto &v = cache1[index];

v.push_back(i);

}

int x = 0, y = 0;

for (int i = 0; i < nums.size(); i++)
{
int delta = target - nums[i];
if (delta < 0)continue;
if (cache1[delta].size() == 0)continue;
if (cache1[nums[i]].size() == 0)continue;
x = cache1[delta][0];
int ii = 0;
if (cache1[delta].size() != 1)ii = 1;

for (; ii < cache1[delta].size(); ii++)
{

if (cache1[delta][ii] != 0)
{

y = cache1[nums[i]][ii];

if (x > y) return{ y, x };

return{ x, y };
}
}

}
return{ -1, -1 };
}
};

``````

``````
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
std::map<int, int>m;
for (int i = 0; i < nums.size(); i++)
{
m[nums[i]] = i;//缓存 数字的index
}

for (int i = 0; i < nums.size(); i++)
{
int delta = target - nums[i];
auto res= m[delta];

if (res!=0)
{
return{ i, res};
}
}

}
};``````

© 著作权归作者所有

### 梦想游戏人

leetcode题解(二叉树和递归问题)

2018/06/26
0
0
Leetcode_Problem 16_3 Sum Closest

quiet_girl
2018/03/09
0
0
LeetCode 64. Minimum Path Sum

dby_freedom
2018/10/11
0
0
[算法][LeetCode] Dynamic Programming（DP）动态规划

2017/10/19
0
0
LeetCode日记2

LeetCode-5 思路： （1）最后用子字符串操作返回string。 return s.substr(startpos, maxlength)； （2）回文串的判断： 1）首先找出回文串中间连续的重复的字符。 2）再向两边进行判断 （3...

fxdhdu
2015/10/19
53
0

linux 扩展lv

hnairdb
4分钟前
0
0

mingle
5分钟前
0
0

6分钟前
0
0
word文档处理成富文本生成sql语句导入mysql

S三少S
13分钟前
29
0
WAF开放规则定义权：专家策略+用户自定义策略=Web安全

17分钟前
0
0