题解 | #两数之和#

import java.util.*;


public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    //n*logn
    public int[] twoSum (int[] numbers, int target) {
        if(numbers == null || numbers.length==0) {
            return null ;
        }
        int[] newArr = Arrays.copyOf(numbers,numbers.length) ;
        quikS(newArr , 0 , newArr.length-1);
        int s = 0 ;
        int e = newArr.length-1 ;
        int [] res = new int[2] ;
        while(s < e) {
            int t = newArr[s] + newArr[e] ;
            if(t == target) {
                res = findIndexByValue(numbers ,newArr[s],newArr[e]) ;
                break ;
            } else if(t > target) {
                e -- ;
            } else {
                s ++ ;
            }
        }
        return res ;
        
    }
    //按照值来查索引，并且去除重复的索引 n
    public int[] findIndexByValue(int arr[] ,int value1 , int value2) {
        int r1 = -1 ;
        int r2 = -1 ;
        for(int i = 0 ; i < arr.length ; i ++) {
            if(arr[i] == value1) {
                r1 = i ;
                break ;
            }
        }
        for(int i = 0 ; i < arr.length ; i ++) {
            if(arr[i] == value2 && i != r1) {
                r2 = i ;
                break ;
            }
        }
        int[] res = new int[2] ;
        if(r1 > r2) {
            res[0] = r2+1 ;
            res[1] = r1+1 ;
        } else {
            res[0] = r1+1 ;
            res[1] = r2+1 ;
        }
        return res ;
    }
    //快排nlogn
    public void quikS(int[] arr , int start , int end) {
        if(start > end) {
            return ;
        }
        int s = start ;
        int e = end ;
        int t = arr[start] ;
        while(s < e) {
            while(s < e && arr[e] >= t) {
                e -- ;
            }
            if(s < e) {
                arr[s] = arr[e] ;
                s ++ ;
            }
            while(s <e && arr[s] <= t) {
                s ++ ;
            }
            if(s < e) {
                arr[e] = arr[s] ;
                e -- ;
            }
        }
        arr[s] = t ;
        quikS(arr,start,s-1) ;
        quikS(arr,s+1,end) ;
    }
}