题解 | #两数之和#

两数之和

http://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f

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

一个菜鸟的算法刷题记录 文章被收录于专栏

分享一个菜鸟的成长记录

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 11:30
找工作7个月,投了7000封,3段世界五百强实习,才有一个offer,牛油们肯定比我强吧
码农索隆:不对不对不对,实习经历这么厉害,简历也没少投,问题出在哪呢
点赞 评论 收藏
分享
Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务