【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个数组和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;
}
};
波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 【Leetcode】Two Sum

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡