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

给定一个数组和一个数，在数组中找到两个数，它们的和等于给定数，返回这两个数在数组中的索引。

问题分析

两重循环最简单，但肯定超时。数组排序是必需的，这样可以有一定的次序来求和。但如果顺序查找，就又是两重循环了。

所以，可以以这样的次序查找：从两头，到中间。保留两个指针，左边一个，右边一个，两个指针指向的数相加，会有以下结果和操作：

1. 相加之和等于给定数，成功；
2. 相加之和大于给定数，大了，右边的指针左移，将两数之和减小；
3. 相加之和小于给定数，小了，左边的指针右移，将两数之和加大。

注：参数是引用，排序时要使用拷贝的数组

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    	// 复制数组，因为要排序 
    	vector<int> cp(nums);
    	// 先排序 
        sort(cp.begin(), cp.end());
        int right = cp.size()-1;
        int left = 0;
        while(right > left) {
        	int sum = cp[right] + cp[left];
        	if(sum == target) {
	        	break;
	        } else if(sum < target) { // 数小了，left右移 
        		left++; 
        	} else if(sum > target) { // 数大了，right左移 
	        	right--;	
	        }
        }
        vector<int> r;
        int a=-1,b=-1;
        // 取出索引 
        for(int i=0;i<nums.size();i++) {
        	if(nums[i] == cp[left]&&a==-1) a = i;
        	else if(nums[i] == cp[right]&&b==-1) b = i;
        }
        if(a>b) {
        	int t = a;
        	a=b,b=t;
        }
        r.push_back(a);
        r.push_back(b);
        return  r;
    }
};