leetcode 167 Two Sum II - Input array is sorted

Keagan 發布于2019-08-15 13:44 / 335人閱讀

摘要：同時題目假設每組輸入恰好只有一個答案，并且不能重復使用同一元素。理解這道題是可以用兩層循環蠻力解決的，但是效率太低了。如果這兩個元素和大于目標數組，指針左移如果小于，指針右移。如果等于，則返回這兩個元素的位置記得用數組的數值加一解法

題目詳情

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

GPU云服務器云服務器 two-sum sorted-array Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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