前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-167-Two Sum II-Input array is sorted

leetcode-167-Two Sum II-Input array is sorted

作者头像
chenjx85
发布2018-05-21 18:41:08
5000
发布2018-05-21 18:41:08
举报
文章被收录于专栏:chenjx85的技术专栏

题目描述:

Given an array of integers that is already sorted in ascending order, 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 and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

要完成的函数:

vector<int> twoSum(vector<int>& numbers, int target) 

说明:

1、数组不降序(在测试样例中见过输入是一连串的0),给定目标,找到两个数的和为目标,返回这两个数的坐标。坐标要小的在前,大的在后,从1开始。

2、题目保证必定能找到这样的两个元素满足条件,且同一个元素不能用两次。

3、题目要求看到这里,最初始的想法是双重循环,这种做法能够把这道题作出来,但是提交之后超时了。

4、既然简单粗暴的双重循环不行,那就单层循环+二分查找。提交完之后击败21.32%的cpp submissions,看来还有优化的空间。这里有个地方要注意一下,不能使用条件numbers[i]<=target,因为numbers里面的数不一定都是正数。

5、到discuss区看一下大神的做法,看到了一个简洁的代码如下。

代码语言:javascript
复制
vector<int> twoSum(vector<int>& numbers, int target) 
{
    int lo=0, hi=numbers.size()-1;
    while (numbers[lo]+numbers[hi]!=target)
  {
        if (numbers[lo]+numbers[hi]<target)
     {
            lo++;
        }
     else
     {
            hi--;
        }
    }
    return vector<int>({lo+1,hi+1});
}

  代码来自于leetcode用户allbugs(反向毒奶?)。侵删。

     这种做法可以说是很简洁了。单层循环+二分查找还是有点浪费时间,没有很好地利用二分查找过程中积累的信息。

  这种算法打败了56.40%的cpp submissions。

     附上笔者本人的代码,供感兴趣的朋友参考。

代码:(单层循环+二分查找)

代码语言:javascript
复制
  int binarysearch(vector<int>& nums,int a,int b)
    {int min=b+1,max=nums.size()-1;//从b+1开始找,排除同一个元素用两次的情况,并且节省时间
        int mid=(min+max)/2;
        while(min<=max)
        {
            if(nums[mid]==a)
                return mid;
            if(nums[mid]<a)
            {
                min=mid+1;
            }
            else
            {
                max=mid-1;
            }
            mid=(min+max)/2;
        }
        return -1;//如果没有找到返回-1
    }
    vector<int> twoSum(vector<int>& numbers, int target) 
    {int j;
        for(int i=0;i<numbers.size();i++)
        {
            j=binarysearch(numbers,target-numbers[i],i);if(j!=-1)
            {
                if(i>j)
                {
                    vector<int>result{j+1,i+1};return result;
                }
                else if(i<j)
                {
                    vector<int>result{i+1,j+1};return result;
                }
            }
        }    
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-04-10 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 要完成的函数:
  • 说明:
  • 代码:(单层循环+二分查找)
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档