专栏首页chenjx85的技术专栏leetcode-167-Two Sum II-Input array is sorted

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

题目描述:

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区看一下大神的做法,看到了一个简洁的代码如下。

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。

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

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-53-Maximum Subarray(动态规划详解)

    chenjx85
  • leetcode-566-Reshape the Matrix

    chenjx85
  • leetcode-209-长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。

    chenjx85
  • 【LeetCode】 两数之和 II - 输入有序数组

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • LeetCode 40. 组合总和 II(排列组合 回溯)

    给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

    Michael阿明
  • 【leetcode算法-搜索插入位置】

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    用户5640963
  • 吐槽版︱MRO-Microsoft R Open快捷键+界面识别+功能设置

    因为用的是中文界面,发现翻译还是有点误差的。一般“交互执行”才能run出来。点击是可以的,但是快捷键在哪呢?

    素质
  • leetcode486. Predict the Winner

    假设有一个正整数数组,两名玩家轮流从里面取数组,玩家1先取,玩家2后取,要求判断出玩家1是否一定能够取胜?

    眯眯眼的猫头鹰
  • Apache Phoenix 的安装与使用

    Apache Phoenix 是 HBase 的开源 SQL 皮肤,可以使用标准的JDBC 的APIs去代替常规的HBase 客户端的APIs去创建表,插入数据...

    ZHANGHAO
  • 【USACO 1.5】Prime Palindromes

    饶文津

扫码关注云+社区

领取腾讯云代金券