`
SunnyYoona
  • 浏览: 361585 次
社区版块
存档分类
最新评论

[LeetCode]1.Two Sum

 
阅读更多

【题目】

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


分享到:
评论

相关推荐

    LeetCode 1.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, and you may not use the same ...

    lrucacheleetcode-leetcode:leetcode

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

    程序员面试宝典LeetCode刷题手册

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

    leetcode所有报错-leetcode:leetcode

    Sum 1.指针的用法 需要通过函数改变外部非全局变量时,需要在形参里用指针声明,然后在函数内用*a=2的方式操作 2.Code::Blocks报错,leetcode服务器通过,未知原因 3.leetcode要求函数返回数组用malloc,例int* ret ...

    leetcode答案-LeetCode_1_TwoSum:LeetCode_1_TwoSum

    答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...

    离线和leetcode-leetcode-cn-cli:为leetcode-cn.com工作

    离线和leetcode leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站!...⦙⦙⦙⦙⦙⦙⦙⦙ ...leetcode.com。...leetcode ...leetcode ...leetcode ...leetcode ..../two-sum.cpp

    Leetcode two sum java 解法

    Leetcode two sum java 解法

    leetcode1.两数之和

    题目描述 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。... vector twoSum(vector& nu

    leetcode 1.两数之和

    题目 链接:https://leetcode-cn.com/problems/two-sum 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。... vector twoSum(vector& n

    leetcodeoj调试-LeetCode:力码

    1. Two Sum 其他OJ的第一题一般都是A+B Problem,看题目名字 我也以为是那种水水的题目,最后发现并不是那么简单。 最开始直接在网页上面写了一个暴力方法求解的代码, 超时了。后面减小了循环内的运算量才过,不过...

    leetcode算法题主函数如何写-leetcode:leetcode_solution

    1.Two Sum python中的hashmap用字典实现,可以用get方法获取key对应的value,用is not None判断是否在hashmap中. PS:用in/not in来判断是否在list中。list获取特定元素的索引:nums.index(item) 带索引的迭代: for ...

    0-leetcode:leetcode练习:twosum问题;addtwonumbers问题;reverse integer问题;最大不重复子字符串长度问题等,详细见readme.md;

    leetcode leetcode练习 twosum 问题 ;add two numbers问题;reverse integer问题;最大不重复子字符串长度问题;atoi问题;

    js代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum

    js代码-1. 两数之和 [简单] https://leetcode-cn.com/problems/two-sum

    Two Sum leetcode c++

    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)...

    leetcode2-leetcode-training:算法训练

    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'

    LeetCode最全代码

    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-practice:算法实践

    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-2.6.1:leetcode-cli-2.6.1

    离线和leetcode leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站!...⦙⦙⦙⦙⦙⦙⦙⦙ ...leetcode.com。...leetcode ...leetcode ...leetcode ...leetcode ..../two-sum.cpp

    leetcode2sumc-leetcode:leetcode.com的解决方案

    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 以...

    leetcode-python:这是我的python的leetcode解决方案

    窗口总和610.TwoSum-差等于目标228.链表中间464.排序整数II 5.Kth最大Elemenet 607.Two Sum III-数据结构设计539.移动零点608.二次加和II 102.链表周期103.LinkedList周期II 380.两个链表的交集148.颜色排序894.煎饼...

Global site tag (gtag.js) - Google Analytics