Two Sum--LeetCode

我会带着你远行 2022-08-07 10:52 24阅读 0赞

# 题目： #

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers=\{2, 7, 11, 15\}, target=9  
Output: index1=1, index2=2

思路：判断一个数是否是一个数组中两个数的和，首先把数组排序，时间复杂度为o(nlogn),然后对已每一个元素，查看目标元素和此元素之差是否在数组内，查找使用二分查找，总体时间复杂度为0(nlogn) 其实在查找的时候也可以使用O(n)时间复杂度，使用两个指针，一个指针从前往后，一个指针从后往前，根据两个元素之和和目标元素的比较结果来移动指针。

#include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    using namespace std;
    /*
    判断一个数是一个数组中的两个数的和 
    */ 
    
    pair<int,int> TwoSum(vector<int>& vec,int target)
    {
    	sort(vec.begin(),vec.end()); //首先进行排序 
    	int i;
    	int mid;
    	int lev;
    	int low,high;
    	for(i=0;i<vec.size();i++)
    	{
    		lev = target -vec[i]; //使用二分查找 查看lev是否在数组中 
    		low = 0;
    		high = vec.size();
    		while(low <= high)
    		{
    			mid = low + (high-low)/2;
    			if(lev == vec[mid])
    				break;
    			else if(vec[mid]>lev)
    				high = mid-1;
    			else
    				low = mid+1;
    		}
    		if(lev == vec[mid] && mid !=i)
    			return pair<int,int>(min(mid,i)+1,max(mid,i)+1);
    	}
    }
    
    int main()
    {
    	int array[]={2,7,11,15};
    	vector<int> vec(array,array+sizeof(array)/sizeof(int));
    	pair<int,int> pos = TwoSum(vec,9);
    	cout<<pos.first<<"  "<<pos.second<<endl;
    	return 0;
    }