程序员人生 网站导航

【Leetcode】Two Sum

栏目:php教程时间:2016-10-10 08:13:02

问题描写

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个数组和1个数,在数组中找到两个数,它们的和等于给定数,返回这两个数在数组中的索引。

问题分析

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

所以,可以以这样的次序查找:从两头,到中间。保存两个指针,左侧1个,右侧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; } };
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐