LC01- 两数之和

题目链接

https://leetcode-cn.com/problems/two-sum/

思路

1:暴力法,时间复杂度o(n^2) 空间复杂度o(1)

 public int[] twoSum(int[] nums, int target) {
        if(nums == null || nums.length == 0){
            return new int[]{};
        }
        for(int i = 0 ; i < nums.length; i++){
            for(int j = i+1; j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{};
    }

2: HashMap表法 时空复杂度 o(n) o(n)

    //存储数值和下标
    //以后缓存都叫cache吧
    Map<Integer,Integer> cache = new HashMap<>();
    public int[] twoSum(int[] nums, int target) {
    //进来先判断参数
       if(nums == null || nums.length == 0){
            return new int[]{};
        }
       for(int i = 0; i < nums.length; i++){
           //假定如果已经存在，直接返回当前的索引，再根据key取之前的值索引返回
           if(cache.containsKey(target - nums[i])){
               return  new int[]{i,cache.get(target - nums[i])}; 
           }
           //不存在一直追加呗
           cache.put(nums[i],i);
       }
       return new int[]{};
    }