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


	}
};