题解 | #和为S的两个数字#

import java.util.ArrayList;

import java.util.HashMap;

public class Solution {

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {

    ArrayList<Integer> arr = new ArrayList<>();
    int len = array.length;
    // 方法一 暴力解法 时间复杂度O(n*2) 空间复杂度O(1)
    for(int i=0;i<len-1&&array[i]<sum;++i){
        for(int j=i+1;j<len&&array[j]<sum;++j){
            if(array[i]+array[j]==sum){
                arr.add(array[i]);
                arr.add(array[j]);
                return arr;
            }
        }
    }
    
    // 方法二 利用数组升序的特点
    int l=0, r=len-1;
    while(r>0 && array[r]>=sum) r--;
    while(l<r){
        if(array[l]+array[r]<sum)
            l++;
        else if(array[l]+array[r]>sum)
            r--;
        else{
            arr.add(array[l]);
            arr.add(array[r]);
            return arr;
        }
    }
    
    //方法三 哈希
    HashMap<Integer,Integer> map = new HashMap<>();
    for(int i=0;i<len;++i){//提前把小于sum的元素存入哈希中
        if(array[i]>sum)
            break;
        map.put(array[i],1);
    }
    for(int i=0;i<len;++i){
        if(map.containsKey(sum-array[i])){//sum-a在哈希中存在，说明找到了
            arr.add(array[i]);
            arr.add(sum-array[i]);
            return arr;
        }
    }
    return arr;
}

}