leetcode 167 Two Sum II - Input array is sorted

Keagan 发布于2019-08-15 13:44 / 239人阅读

摘要：同时题目假设每组输入恰好只有一个答案，并且不能重复使用同一元素。理解这道题是可以用两层循环蛮力解决的，但是效率太低了。如果这两个元素和大于目标数组，指针左移如果小于，指针右移。如果等于，则返回这两个元素的位置记得用数组的数值加一解法

题目详情

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

题目的输入是一个已经按照升序排列的整数数组和一个目标数字。
要求的输出是：数组中加和恰好为目标数字的两个元素的位置（这里的位置不从0开始计算）。
同时题目假设每组输入恰好只有一个答案，并且不能重复使用同一元素。

理解

这道题是可以用两层循环蛮力解决的，但是效率太低了。我们如何能得到一个复杂度为n的解法呢？
我们可以声明两个指针left，right分别指向数组中最小的元素、最大的元素。
如果这两个元素和大于目标数组，right指针左移；如果小于，left指针右移。如果等于，则返回这两个元素的位置（记得用数组的index数值加一）

解法

    public int[] twoSum(int[] numbers, int target) {

        int[] res = new int[2];
        if(numbers == null || numbers.length <2){
            return res;
        }
        
        int left = 0;
        int right = numbers.length-1;        
        while(left < right){
            int temp = numbers[left] + numbers[right];
            if(temp == target){
                res[0] = left + 1;
                res[1] = right +1;
                return res;
            }else if(temp >target){
                right --;
            }else{
                left++;
            }
        }
        
        
        return res;
    }

私有云专线服务 two-sum sorted-array Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68286.html

LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

张春雷 2019-08-16 18:29 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

Me_Kun 2019-07-31 11:26 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
leetcode部分题目答案之JavaScript版

摘要：自己没事刷的一些的题目，若有更好的解法，希望能够一起探讨项目地址自己没事刷的一些LeetCode的题目，若有更好的解法，希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0