package arrays;

import java.util.Arrays;
import java.util.HashMap;

/**题目:
 * 给定一个数组,要求返回和为某个值的两个数字的下标
 * y: 1 2 3 4 5 6 7 10
 * [2,6]
 * @Author Gavin
 * @date 2021年12月07日 21:39
 */
public class array_1 {
 //第一种就是暴力破解法,两重循环进行取值
 //Time: O(n^2) Space:O(1)
 public Integer[] solution(Integer[] array,int sum){
 for (int i = 0; i <array.length ; i++) {
 for (int j=i+1;j<array.length;j++){
 if(array[i]+array[j]==sum) return new Integer[]{i,j};
 }
 }
 return new Integer[]{-1,-1};
 }
 //第二种,需要借助hashmap来存储下标值,这样时间复杂度就变为了O(1)
 //Time:O(1) Space:O(n)
 public int[] solution(int[] array,int sum){
 HashMap<Integer,Integer> po=new HashMap<>();
 for (int i = 0; i < array.length; i++) {
 int needNum=sum-array[i];
 if(po.containsKey(needNum)){
 return new int[]{po.get(needNum),i};
 }
 po.put(array[i],i);//注意这里是比较关键的,把数组的值和下标存储到hashmap中
 }
 return new int[]{-1,-1};
 }
}