【题目】
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
【分析】
类似于剑指Offer之和为S的两个数字
【代码】
/*********************************
* 日期:2015-01-15
* 作者:SJF0115
* 题目: 1.Two Sum
* 网址:https://oj.leetcode.com/problems/two-sum/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> result;
vector<int> num = numbers;
int count = numbers.size();
if(numbers.empty()){
return result;
}//if
// 排序
sort(numbers.begin(),numbers.end());
// 二分查找变形
for(int i = 0,j = count-1;i < j;){
int sum = numbers[i] + numbers[j];
// 找到目标
if(sum == target){
return FindIndex(num,numbers[i],numbers[j]);
}
// 当前和大于目标,需要变小一些
else if(sum > target){
j--;
}
// 当前和小于目标,需要变大一些
else{
i++;
}
}//for
return result;
}
private:
// 寻找下标
vector<int> FindIndex(vector<int> &numbers,int num1,int num2){
int count = numbers.size();
vector<int> result;
int index1,index2;
bool flag1 = false,flag2 = false;
for(int i = 0;i < count;++i){
if(flag1 == false && numbers[i] == num1){
index1 = i+1;
flag1 = true;
}
else if(flag2 == false && numbers[i] == num2){
index2 = i+1;
flag2 = true;
}
}//for
// 交换 使index1 < index2
if(index1 > index2){
int tmp = index1;
index1 = index2;
index2 = tmp;
}//if
result.push_back(index1);
result.push_back(index2);
return result;
}
};
int main(){
Solution solution;
vector<int> num;
num.push_back(0);
num.push_back(4);
num.push_back(3);
num.push_back(0);
//num.push_back(15);
int target = 0;
// 查找
vector<int> vec = solution.twoSum(num,target);
// 输出
cout<<"Index1->"<<vec[0]<<" Index2->"<<vec[1]<<endl;
return 0;
}
分享到:
相关推荐
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, and you may not use the same ...
1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. Palindrome Number 11. Container ...
1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to ...
Sum 1.指针的用法 需要通过函数改变外部非全局变量时,需要在形参里用指针声明,然后在函数内用*a=2的方式操作 2.Code::Blocks报错,leetcode服务器通过,未知原因 3.leetcode要求函数返回数组用malloc,例int* ret ...
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
离线和leetcode leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站!...⦙⦙⦙⦙⦙⦙⦙⦙ ...leetcode.com。...leetcode ...leetcode ...leetcode ...leetcode ..../two-sum.cpp
Leetcode two sum java 解法
题目描述 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。... vector twoSum(vector& nu
题目 链接:https://leetcode-cn.com/problems/two-sum 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。... vector twoSum(vector& n
1. Two Sum 其他OJ的第一题一般都是A+B Problem,看题目名字 我也以为是那种水水的题目,最后发现并不是那么简单。 最开始直接在网页上面写了一个暴力方法求解的代码, 超时了。后面减小了循环内的运算量才过,不过...
1.Two Sum python中的hashmap用字典实现,可以用get方法获取key对应的value,用is not None判断是否在hashmap中. PS:用in/not in来判断是否在list中。list获取特定元素的索引:nums.index(item) 带索引的迭代: for ...
leetcode leetcode练习 twosum 问题 ;add two numbers问题;reverse integer问题;最大不重复子字符串长度问题;atoi问题;
js代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum
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)...
leetcode 2 leetcode-训练 算法训练。 java $: javac hello.java java ...leetcode ...leetcode ...leetcode ...leetcode ...1.two-sum.cpp leetcode test 1.two-sum.cpp leetcode test 1.two-sum.cpp -t '[1,2,3]\n3'
15 | [3 Sum](https://leetcode.com/problems/3sum/) | [C++](./C++/3sum.cpp) [Python](./Python/3sum.py) | _O(n^2)_ | _O(1)_ | Medium || Two Pointers 16 | [3 Sum Closest]...
leetcode。 3sum leetcode-练习 算法实践 15. 3和 给定一个由 n 个整数组成的数组 nums,nums ...[-1, ...1, ...-1, ...[-1, ...1], [-1, -1, ...search_sum(target,num_idx,nums):#...two elements sum up to target ls=[] for i in ra
离线和leetcode leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站!...⦙⦙⦙⦙⦙⦙⦙⦙ ...leetcode.com。...leetcode ...leetcode ...leetcode ...leetcode ..../two-sum.cpp
leetcode_001_two_sum_test.c 有 5 个断言 sh test.sh 001 ..... 添加 -a 以运行所有测试(助手除外)。 sh test.sh all leetcode_001_two_sum_test.c ..... leetcode_002_add_two_numbers_test.c .... 添加 -b 以...
窗口总和610.TwoSum-差等于目标228.链表中间464.排序整数II 5.Kth最大Elemenet 607.Two Sum III-数据结构设计539.移动零点608.二次加和II 102.链表周期103.LinkedList周期II 380.两个链表的交集148.颜色排序894.煎饼...