Two Sum II - Input Array Is Sorted 兩數(shù)之和 II - 輸入有序數(shù)組

問題描述：

給你一個(gè)下標(biāo)從 1 開始的整數(shù)數(shù)組 numbers ，該數(shù)組已按 非遞減順序排列 ，請你從數(shù)組中找出滿足相加之和等于目標(biāo)數(shù) target 的兩個(gè)數(shù)。如果設(shè)這兩個(gè)數(shù)分別是 numbers[index1] 和 numbers[index2] ，則 1 <= index1 < index2 <= numbers.length 。

以長度為 2 的整數(shù)數(shù)組 [index1, index2] 的形式返回這兩個(gè)整數(shù)的下標(biāo) index1 和 index2。

你可以假設(shè)每個(gè)輸入 只對應(yīng)唯一的答案 ，而且你 不可以 重復(fù)使用相同的元素。

你所設(shè)計(jì)的解決方案必須只使用常量級的額外空間。

$$\begin{gathered} 2<=numbers.length<=3?10^4 \\ ?1000<=numbers[i]<=1000 \\ numbers按非遞減順序排列 \\ ?1000<=target<=1000 \\ 僅存在一個(gè)有效答案 \end{gathered}$$

分析

第一個(gè)應(yīng)該想到的就是暴力，時(shí)間復(fù)雜度$O(N^2)$.

暴力雖然時(shí)間復(fù)雜度高，但是絕對可以拿捏，不需要考慮其他特殊情況。

改進(jìn)：

因?yàn)樵瓟?shù)組是一個(gè)規(guī)律的有序數(shù)組，所以在找另一個(gè)數(shù)的時(shí)候，就可以二分了。時(shí)間復(fù)雜度$O(NLogN)$.

特點(diǎn)：比較快，但是場景有限制，對編碼能力有一定門檻。

再改進(jìn)：

雙指針，該方法還是基于有序數(shù)組，

• 從2個(gè)端點(diǎn)開始找，
• 如果$sum==target$,說明找到了一個(gè)合法的pair。
• 否則$sum>target$,那就需要把右端點(diǎn)像左移。
• 如果$sum<target$,那就需要把左端點(diǎn)向右移。

特點(diǎn)：這個(gè)比二分更快，時(shí)間復(fù)雜度$O(N)$,也是對場景有限制。

Two Sum 雖然簡單，但是變種太多。如果不是有序的數(shù)組，這個(gè)時(shí)候，就不能直接使用二分和雙指針了。

代碼

二分

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for(int i = 0;i<n; i++){
            int idx = find(numbers,i+1,n-1,target-numbers[i]);
            if(idx!=-1){
                return new int[]{i+1,idx+1};
            }
        }
        return new int[0];
    }

    public int find(int[] arr,int l,int r,int tar){
        int mid = 0;
        while(l<=r){
            mid = l+ (r-l)/2;
            if(arr[mid]== tar) return mid;
            if(arr[mid]>tar) r = mid-1;
            else l = mid+1;
        }        
        return -1;
    }
}

時(shí)間復(fù)雜度$O(N\log N)$

空間復(fù)雜度$O(1)$

雙指針

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l=0,r = numbers.length-1;
        while(l<r){
            int x = numbers[l]+numbers[r];
            if(x== target){
                return new int[]{l+1,r+1};
            }
            if(x>target) r--;
            else l++;
        }
        return new int[0];
    }
}

時(shí)間復(fù)雜度$O(N)$

空間復(fù)雜度$O(1)$

Tag

Array

Two pointer

Binary Search文章來源地址http://www.zghlxwxcb.cn/news/detail-537678.html

到了這里，關(guān)于【算法】Two Sum II - Input Array Is Sorted 兩數(shù)之和 II - 輸入有序數(shù)組的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！