记事本刷算法哇

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