首页 > 其他 > 详细

leetcode-1-两数之和

时间:2020-02-25 11:10:12      阅读:68      评论:0      收藏:0      [点我收藏+]

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

方法一:暴力法

遍历每一个元素,并查找是否存在一个值与target-x相等的目标元素

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[j] == target - nums[i])
                //返回一个两个数的索引数组    
                return new int[]{i,j};
            }
        }
        //抛出超时异常
        throw new RuntimeException("No two sum solution");
    }
}

方法二:用hashmap空间换取时间

通过空间换去速度的方式,我们可以将查找时间从O(n)降到O(1),支持以近似恒定的时间进行快速查找近似的意思,是因为一旦发生冲突,查找时间可能会退化到O(n),一个简单的实现使用了两次迭代,在第一次迭代中,我们将每一个元素和它的索引添加到表中,然后在第二次迭代中,我们将检查每个元素所对应的目标元素,是否存在于表中,注意该目标元素不能为本身

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //定义一个新的哈希表
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            //map.containsKey方法表示,判断Map集合对象中是否包含指定的键名
            if (map.containsKey(complement)) {
                //先遍历数组,查找值,如果不存在相应的值,然后将对应的值,加到map里
                //遍历数组 nums,i 为当前下标,每个值都判断map中是否存在 target-nums[i] 的 key 值
                //判断map中是否存在,返回找到的数组下标,map.get用来获取对应值的索引 
                return new int[] { map.get(complement), i };
            }
            //如果没找相应的值,就将当前的(nums[i],i)存入map
            map.put(nums[i], i);
        }
        //抛出异常
        throw new IllegalArgumentException("No two sum solution");
    }
}

 

leetcode-1-两数之和

原文:https://www.cnblogs.com/lss0204/p/12360058.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!