康瑞部落

Two Sum

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

大体思路：
（1）最简单的办法是两重循环，暴力枚举。时间复杂度O(n2)，空间复杂度为O(1)，但会产生超时问题。代码略。

（2）先给数组排序（快排），并记录原有元素的下标，然后通过二分法找到下一个加数。由于排序的时间复杂度为O（nlogn），记录原有元素的下标的空间为O(n)，因此整体的时间复杂度为O(nlogn)，空间复杂度为O(n)。

class Solution {
public:
	vector<int> twoSum(vector<int> &numbers, int target) {
		vector<int> result;

		int count = numbers.size();
		vector<int> originIndex;
		for (int i = 0; i < count; i++){
			originIndex.push_back(i);
		}
		sortVector(numbers, originIndex, 0, count - 1);

		for (int i = 0; i < count; i++){
			int j = find(numbers, i + 1, count - 1, target - numbers[i]);
			if (j >= 0){
				if (originIndex[i]< originIndex[j]){
					result.push_back(originIndex[i] + 1);
					result.push_back(originIndex[j] + 1);
				}
				else{
					result.push_back(originIndex[j] + 1);
					result.push_back(originIndex[i] + 1);
				}
				break;
			}
		}

		return result;
	}
private:
	void sortVector(vector<int> &numbers, vector<int> &originIndex, int start, int end){
		if (start >= end){
			return;
		}
		int flagIndex = (start + end) / 2;
		swap(numbers, flagIndex, end);
		swap(originIndex, flagIndex, end);
		flagIndex = end;
		int i = start, j = flagIndex;
		do{
			while (i < j && numbers[i] <= numbers[j]) i++;
			if (i < j){
				swap(numbers, i, j);
				swap(originIndex, i, j);
				flagIndex = i;
				while (i < j && numbers[i] <= numbers[j]) j--;
				if (i < j){
					swap(numbers, i, j);
					swap(originIndex, i, j);
					flagIndex = j;
				}
			}
		} while (i < j);

		sortVector(numbers, originIndex, start, flagIndex - 1);
		sortVector(numbers, originIndex, flagIndex + 1, end);
	}
	void swap(vector<int> &numbers, int i, int j){
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}
	int find(vector<int> &numbers, int start, int end, int target){
		int result = -1;
		if (start <= end){
			int middle = (start + end) / 2;
			if (numbers[middle] < target){
				result = find(numbers, middle + 1, end, target);
			}
			else if (numbers[middle] > target){
				result = find(numbers, start, middle - 1, target);
			}
			else{
				result = middle;
			}
		}
		return result;
	}
};

（3）用哈希表来存储下标。这只是适合于数组没有重复的情况。注意有个陷阱。

class Solution {
public:
	vector<int> twoSum(vector<int> &numbers, int target) {
		vector<int> result;

		int count = numbers.size();
		
		map<int, int> valueToIndex;
		for (int i = 0; i < count; i++){
			valueToIndex.insert(map<int, int>::value_type(numbers[i], i));
		}

		map<int, int>::iterator it;
		for (int i = 0; i < count; i++){
			it = valueToIndex.find(target - numbers[i]);
			if (it != valueToIndex.end()){
				int j = it->second;
				if(i == j){ //陷阱
				    continue;
				}
				if (i < j){
					result.push_back(i+1);
					result.push_back(j+1);
				}
				else{
					result.push_back(j + 1);
					result.push_back(i + 1);
				}
				break;
			}
		}

		return result;
	}
};

二次刷题（2015-08-17）

较为简单的是hash法

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> valToIndex;
        for(int i=0; i<nums.size(); i++){
            valToIndex[nums[i]] = i;
        }
        for(int i=0; i<nums.size(); i++){
            if(valToIndex.find(target - nums[i])!=valToIndex.end() && valToIndex[target - nums[i]]!=i){
                int index1 = i + 1;
                int index2 = valToIndex[target - nums[i]] + 1;
                return index1 > index2 ? vector<int>({index2, index1}) : vector<int>({index1, index2});
            }
        }
        return vector<int>();
    }
};