牛客题霸两数之和Java题解

牛客题霸两数之和Java题解
https://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f?tpId=117&&tqId=34983&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
方法1：遍历数组，暴力破解
解题思路：用两个for循环遍历数组，当numbers[i] + numbers[j] == target时，输出数的下标。如果不存在就返回null
注意：返回的下标是从1开始的

import java.util.*;

public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        int n = numbers.length;
        for (int i = 0; i < n; ++i) {          //遍历数组
            for (int j = i + 1; j < n; ++j) {
                if (numbers[i] + numbers[j] == target) {  //当找到和为target的两数时，输出对应的下标
                    return new int[]{i+1, j+1};    //注意：返回的下标要从1开始
                }
            }
        }
        return null;
    }
}

方法2：HashMap
解题思路：利用HashMap存储数在numbers[]数组中的值和下标，然后通过for循环遍历数组，当前数为numbers[i]，如果target - numbers[i]等于在HashMap中的key值，那么说明数组中存在两个和为target的数，返回值在数组中的下标。如果不存在就返回null。注意：返回的下标从1开始。

import java.util.*;

public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
     public int[] twoSum (int[] numbers, int target) {
       HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< numbers.length; i++) {
            int num = target - numbers[i];
            if(map.containsKey(num)) {     //如果hashmap中包含target - numbers[i]，则找到这两个数，返回下标
                return new int[] {map.get(num)+1,i+1};   //注意：返回的下标要从1开始
            }
            map.put(numbers[i], i);        //将numbers[]数组中的值和下标存入hashmap中
        }
        return null;
    }
}

方法3：排序+双指针
解题思路：先将原数组复制到数组nums中，然后将数组nums按从小到大排序，然后利用双指针，一个指向头，一个指向尾进行遍历，找出和为target的两个数，再在原数组中将这两个数的下标找出来。

import java.util.*;

public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        int [] nums = new int[numbers.length];
        System.arraycopy(numbers,0,nums,0,numbers.length);  //将原数组复制到数组nums中
        Arrays.sort(nums);  //对数组nums按从小到大排序
        int i = 0;
        int j = nums.length-1;
        int num1 = 0;
        int num2 = 0;
        while(i<j){
            if((nums[i]+nums[j])>target){   //如果两数之和大于target，j--
                j--;
            }else if((nums[i]+nums[j])<target){  //如果两数之和小于target，i++
                i++;
            }else{                //如果两数之和等于target，则将这两个数保存在num1和num2中
                num1 = nums[i];
                num2 = nums[j];
                break;           
            }
        }
        int index1=-1;
        int index2=-1;
        for(int k = 0;k<numbers.length;k++){  //在原数组中查找值对应的下标
            if(numbers[k]==num1 && index1==-1){  //index1中存首次numbers[k]==num1时，k的值
                index1 = k;
                continue;    //两个数的下标是不同的，num1的下标为k，num2的下标就一定不会是k了，所以直接continue，进行下次循环
            }
            if(numbers[k]==num2 && index2==-1){   //index2中存首次numbers[k]==num2时，k的值
                index2 = k;
            }
            if(index1>-1 && index2>-1){  //如果在numbers[]数组中找到两个数，则跳出循环
                break;
            }
        }


        if(index1<index2){      
            return new int[]{index1+1,index2+1};
        }else{
            return new int[]{index2+1,index1+1};
        }
    }
}