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