记事本刷算法哇

【2020.7.5】LC148 Two-sum

题目描述

给出一个整数数组，请在数组中找出两个加起来等于目标值的数，

你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的

假设给出的数组中只存在唯一解

例如：

给出的数组为 {2, 7, 11, 15},目标值为9
输出 ndex1=1, index2=2

我的想法很简单，直接暴力两次循环遍历，但它题目的标签是hash

import java.util.Scanner;
public  class TwoSum{
     public int[] solution (int[] numbers, int target) {
        // write code here
        int[] output = new int[2];
        for(int i=0;i<numbers.length;i++){
            for(int j=i+1;j<numbers.length;j++){
                if((numbers[i]+numbers[j])==target)
                {
                    output[0]=i+1;
                    output[1]=j+1;
                    return output;
                }
                else
                    continue;
            }
        }
        return output;
    }
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] temp = line.split(" ");
        int[] input1 = new int[temp.length];
        for(int i=0;i<temp.length;i++){
            input1[i]=Integer.parseInt(temp[i]);
        }
        int target = scanner.nextInt();
        TwoSum twosum = new TwoSum();
        System.out.println(twosum.solution(input1,target)[0]+" "+twosum.solution(input1,target)[1]);
        
    }
}

看了牛客大佬们的解释，恍然大悟，直接先用hashmap存储输入数组的，把数组元素的值作为map的key，把数组的下标作为value，然后再扫描一遍数组，如果hashmap中存在target-input[i]则说明找到了和为target的两个数，如果hashmap中不存在，则说明数组中不存在和为target的两个数。时间复杂度瞬间降到了O(n)了。

public int[] hashsolutioin(int[] numbers,int target){
        HashMap<Integer,Integer> hash = new HashMap<>();
        int[] output = new int[2];
        for(int i=0;i<numbers.length;i++){
            if(hash.containsKey(target-numbers[i])){
                output[0]=hash.get(target-numbers[i])+1;
                output[1]=i+1;
                return output;
            }
            else{
                hash.put(numbers[i],i);
            }
        }
        return output;
    }