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].

常规方法肯定超时，所以用查表来解决。但提交后发现 ERROR，原因是测试数据可能是负数，因此改用 map。

方案一：数组缓存（有缺陷）

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 };
                	}
                };
                

方案二：map 查找（正确解法）

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};
                			}
                		}
                
                
                	}
                };