首页 > 其他 > 详细

[leetcode刷题]—— 哈希表

时间:2021-01-17 19:25:32      阅读:29      评论:0      收藏:0      [点我收藏+]

一、两数之和为给定值

1.两数之和  (easy) 2021-01-16

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

    这,力扣第一题,暴力解法。时间复杂度为O(nlogn),空间复杂度为O(1)。

  如果使用哈希表来储存,先将数组存放进哈希表,然后遍历数组,每访问一个元素,就去哈希表中搜索target - nums[i]。

  再优化算法就是,在遍历数组的时候,先搜索,在存放进哈希表 ,这么做,时间复杂度为O(n),空间复杂度为O(n)。

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++){
                int sum = nums[i] + nums[j];
                if(sum == target){
                    return new int[]{i, j};
                } 
            }
        }
        return null;
    }
}

   下面是使用栈的做法。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{i,  map.get(target - nums[i])};
            }else{
                map.put(nums[i], i);
            }
        }
        return null;
    }
}

 

二、判断数组是否含有重复元素

217.存在重复元素  (easy)2021-01-17

给定一个整数数组,判断是否存在重复元素。

如果存在一值在数组中出现至少两次,函数返回 true 。如果数组中每个元素都不相同,则返回 false 。

使用Set的特性,无序不可重复。添加的时候如果重复添加失败会返回false。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            if(!set.add(nums[i])){
                return true;
            }
        }
        return false;
    }
}

 

三、最长和谐序列

594.最长和谐子序列  (easy) 2021-01-17

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在,给定一个整数数组,你需要在所有可能的子序列中找到最长的和谐子序列的长度。

 下面的代码是使用快慢指针的做法,先给数组排序,然后设置一个快指针一个慢指针,保持在值的差距小于1的距离。

 

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);
        int begin = 0, res = 0;
        for(int end = 0; end < nums.length; end++){
            while(nums[end] - nums[begin] > 1){
                begin++;
            }
            if(nums[end] - nums[begin] == 1){
                res = Math.max(res, end - begin + 1);
            }  
        }
        return res;
    }
}

   下面的代码是使用哈希表的做法。先将数据和存现的频次存放进哈希表,getOrDefault( , )函数图其字面意思,如果存在key = num值就取出其对应的value,不存在就返回一个默认值。然后遍历哈希表。

class Solution {
    public int findLHS(int[] nums) {
    Map<Integer, Integer> countForNum = new HashMap<>();
    for (int num : nums) {
        countForNum.put(num, countForNum.getOrDefault(num, 0) + 1);
    }
    int longest = 0;
    for (int num : countForNum.keySet()) {
        if (countForNum.containsKey(num + 1)) {
            longest = Math.max(longest, countForNum.get(num + 1) + countForNum.get(num));
        }
    }
    return longest;
}
}

 

四、最长连续序列

128.最长连续序列 (hard) 2021-01-17

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

进阶:你可以设计并实现时间复杂度为 O(n) 的解决方案吗?

    我啪的一下一个sort(),很快嗷,然后一个遍历,直接通过,按传统编程,点到即止,我已经赢了。这时候他一个时间复杂度为 O(n)打过来,我大意了,没有闪,我说小力扣你不讲武德,来偷袭我这22岁的老同志,这好吗,这不好。我劝,这位小力扣耗子为汁,好好反思,不要再犯这样的聪明,小聪明啊。

class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        Arrays.sort(nums);
        int max = 0; 
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i] - 1)){  //如果哈希表中存放有nums[i] - 1的数
                map.put(nums[i], map.get(nums[i] - 1) + 1);
                max = Math.max(max, map.get(nums[i] - 1) + 1);
            }else{
                map.put(nums[i], 1);  //如果不存在从1开始计数
                max = Math.max(max, 1);
            }
        }
        return max;
    }
}

  使用set存储,无序可重复的特性。遍历数组,把连续的数全部删除记录最长的连续数就行。

  

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numsSet = new HashSet<>();
        for (Integer num : nums) {
            numsSet.add(num);
        }
        int longest = 0;
        for (Integer num : nums) {
            if (numsSet.remove(num)) {
                // 向当前元素的左边搜索,eg: 当前为100, 搜索:99,98,97,...
                int currentLongest = 1;
                int current = num;
                while (numsSet.remove(current - 1)) current--;
                currentLongest += (num - current);
        // 向当前元素的右边搜索,eg: 当前为100, 搜索:101,102,103,...
                current = num;
                while(numsSet.remove(current + 1)) current++;
                currentLongest += (current - num);
            // 搜索完后更新longest.
                longest = Math.max(longest, currentLongest);
            }
        }
        return longest;
    }
}

 

[leetcode刷题]—— 哈希表

原文:https://www.cnblogs.com/nobita/p/14287624.html

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