本文共 1864 字，大约阅读时间需要 6 分钟。

题目：给定一个数组，以及一个 target 值，target 表示目标和，要求在数组中找到两个数，xi，xj，使得 xi + xj = target。返回值是找到的两个数的下标索引，升序排序。假定至少存在一对解。

分析：对于要处理数组的问题，我们的理想状态都是给定的数组是有序的就好了，在有序后，我们就可以首位各放一个标记。类似于二分查找。

vector
   
     twoSum(vector
    
      &numbers, int target){		vector
     
       re;		if(numbers.size() == 0)			return re;		sort(numbers.begin(), numbers.end());		int small = 0;		int large = numbers.size() - 1;		while (small < large)		{			int sum = numbers[small] + numbers[large];			if(sum == target)			{                                 re.push_back(small + 1);				 re.push_back(large + 1);				 return re;			}			else if(sum < target)				++small;			else			    --large;			}		return re;	}
     
    
   

但是这样排过序后，数组元素的位置就发生了变化，要是再另外去记录下标信息，当然是可以解决的，但是这样又费时又费力，而且要是存储下标信息的话，就可以用hash_map，对于hash，排序的工作就白做了。当然如果题目要求是返回这两个和因子，或者返回是否存在这样的解，这种办法应该还是不错的。时间复杂度就是排序的复杂度。

既然要求值本身与下标对应，就选择map来存储，要速度，就hash，所以最后选hash_map来存储信息。这样的时间复杂度可以在O(N).

vector
   
     twoSum2(vector
    
      &numbers, int target){		vector
     
       re;				if(numbers.size() == 0)			return re;		unordered_map
      
        value_index_map, value_index_multi_map;		for (int i = 0; i < numbers.size(); ++i)		{						unordered_map
       
        ::iterator ifind = value_index_map.find(numbers[i]);			//exited value 			if(ifind != value_index_map.end()){				//get the result or not				if( numbers[i] * 2 == target)				{					re.push_back(ifind->second);					re.push_back(i + 1);					return re;				}			}			//new value			else{                //find the opposite part				ifind = value_index_map.find(target - numbers[i]);				if(ifind != value_index_map.end())				{                    re.push_back(ifind->second);					re.push_back(i + 1);					return re;				}				//add the new one.				else					value_index_map[numbers[i]] = i + 1;    			}		}			return re;	}
       
      
     
    
   

对重复的元素，可以使用两个map，但是对于两个数的和， 其 两个和因子的地位是相同的，而且是相互决定的，所以用一个就可以了。

转载地址：http://yglji.baihongyu.com/