NC61：两数之和/LeetCode：1.两数之和

解法1：暴力枚举

• 直接使用双重循环进行判断，但时间复杂度较大
• 每个当前元素都是与它后面的元素进行相加判断，以此解决了index1<index2的问题

import java.util.*;

public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        int[] re = new int[2];
        for(int i = 0; i<numbers.length-1; i++){
            for(int j = i+1; j<numbers.length; j++){
                if(numbers[i] + numbers[j]  == target){
                    re[0] = i+1;
                    re[1] = j+1;
                    break;
                }
            }
        }
        return re;
    }
}

解法2：哈希法

• 使用HashMap，将目标数target-numbers[i]作为HashMap的key，当前数组元素的下标+1作为value；
• 遍历数组numbers，HashMap为空时先将第一个元素与目标数相减进行put，再对后续的元素进行判断；
• 判断哈希表中是否包含与当前元素相同的key值，有就取出其value值，以此获得该元素对应的下标

import java.util.*;

public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        int[] re = new int[2];
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i<numbers.length; i++){
            if(map.isEmpty()){
                map.put(target-numbers[i],i+1);
                continue;
            };
            if(map.containsKey(numbers[i])){
                re[0] = map.get(numbers[i]);
                re[1] = i+1;
                break;
            }else{
                 map.put(target-numbers[i],i+1);
            }
        }
        return re;
    }
} 

题目地址：https://leetcode-cn.com/problems/two-sum/

• LeetCode中的该题与牛客网的稍有不同，下标是从0开始的
• 优化：先将target - nums[0]放入哈希表中，接着从第二个元素开始遍历，不用每次都进行判断
  

public int[] twoSum(int[] nums, int target) { //哈希法
    int[] res = new int[2];
    //将target-当前值作为哈希表的key，当前的下标作为value
    HashMap<Integer,Integer> map = new HashMap<>();
    map.put(target - nums[0], 0);
    for(int i = 1; i < nums.length; i++){ //遍历数组查找对应的key
        if(map.containsKey(nums[i])){
            res[0] = map.get(nums[i]);
            res[1] = i;
        }else{
            map.put(target - nums[i], i);
        }
    }
    return res;
 }