TwoSum

2019-09-26  本文已影响0人  全村的卡密

坑:用查找表解决该方法,容易忽略值相同数组的情况,并且在值相同的情况下,如何让输出正确。

因为是用onenote做的笔记,所以复制到简书上是图片。


image.png

查找表源码:

public class TwoSum_2{
    public static int[] twoSum(int[] nums, int target) {
        
        final HashMap<Integer,Integer> sumMap = new HashMap<Integer,Integer>();
        int[] noIndex = {-1,-1};
        int complement = 0;

        for(int i = 0;i<nums.length;++i){ //一边创建,一边查找,如果找到就可以提前结束 而不创建整个hash表
            complement = target - nums[i];
            
            //sumMap.put(nums[i],i);这样会先写入哈希表,如果数据为{3,3},key都为3,value = 1会覆盖value = 0,导致i = value
            final Integer value = sumMap.get(complement);
            if(value!=null){
                return new int[]{value,i}; //匿名变量
            }
            sumMap.put(nums[i],i);
        }
        return noIndex;
    }

暴力方法:

public static int[] twoSum(int[] nums, int target) {
        int[] errnum = {-1,-1};
        for(int i = 0;i<nums.length-1;++i){
           for(int j = i+1;j<nums.length;++j){
               if(nums[i]+nums[j] ==target){
                int[] sortnum ={nums[i],nums[j]};
                return sortnum;
               }
           }
       }
       return errnum;
    }
}

官方给出了三种解答:
https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/

上一篇 下一篇

猜你喜欢

热点阅读