数据结构与算法-001-数组-两数之和

两数之和

给定一个数组 n 以及一个目标值 t ，从数组中找到相加等于 t 的两个数字索引

暴力法

解题思路

双层循环，时间复杂度 O(n^2)

public int [] towSum(int [] n,int t){
   // 边界条件
   if(n.length<2){
      return new int[]{};
   }
   int [] result=new int [2];
   for(int i=0;i<n.length;i++){
     for(int j=i+1;j<n.length;j++){
       if(n[i]+n[j]==t){
          result[0]=i;
          result[1]=j;
          return result;
       }
     }
   }
   return new int[0]{};
}

空间换时间

解题思路

使用一个hash存储循环过的值,时间复杂度 O(n)

    public int[] twoSum(int[] nums, int target) {
       // 空间换时间思路
       // 核心要点：目标值=数组值a+数组值b ，即 数组值a/b=目标值-数组值a/b
       // 基于 a=b+c,b=a-c,c=a-b 所以可以将数据存储在一个hashmap的key中，value 存储索引
       // 使用 b=a-c、c=a-b 原理从cache里找到到b/c对应的值即可找到两个b\c的索引
       Map<Integer,Integer> cache=new HashMap();
       for(int i=0;i<nums.length;i++){
           int key=target-nums[i];
           Integer inx=cache.get(key);
           // 找到差值了
           if(inx!=null){
               return new int[]{inx,i};
           }
           cache.put(nums[i],i);
       }
       return new int[]{};
    }