哈希

哈希入门

LeetCode 1. 两数之和

注意添加顺序，先判断再添加...

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //{nums value:index}
        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        for(int i = 0 ; i < nums.length ; i++){
            if(map.containsKey(target-nums[i])){
                res.add(i);
                res.add(map.get(target-nums[i]));
                break;
            }
            map.put(nums[i],i);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
}

2022华为-排队报数

给定整数数组 nums ，要求返回新的数组 counts , counts[i] 为当前位置到数组末尾比自己更小元素个数。

input

第一行是数组长度 N

一个长度 N 的整型数组

1<= nums.length <= 10⁵,40 <=nums[i] <= 110
counts.length=nums.length

output

counts 数组

输入

5
81 82 76 75 100

输出　

2 2 1 0 0

最容易想到的是暴力检索(O(n))，但是 1<=n<=10^5  那最多只能使用O(nlogn)的算法去求解

 从后往前遍历，使用哈希表存储出现过元素值及其出现次数，先判断map中是否存在比当前元素小的值，有则更新次数，并将当前元素put进map

package com.coedes.datastruct.hash.huawei2022101202;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;

/**
 * @description：from https://codefun2000.com/p/P1217
 * @author： wenLiu
 * @create： 2024/4/20 20:07
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(reader.readLine());
        String[] strOfNums = reader.readLine().split(" ");
        int[] nums = new int[N];
        for (int i = 0; i < strOfNums.length; i++) {
            nums[i] = Integer.parseInt(strOfNums[i]);
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        int[] res = new int[N];
        int cnt;
        for (int i = N - 1; i >= 0; i--) {
            cnt = 0;
            for (int j = 40; j < nums[i]; j++) {
                if (map.size() == 0) {
                    break;
                }
                if (map.containsKey(j)) {
                    cnt += map.get(j);
                }
            }
            res[i] = cnt;
            map.merge(nums[i], 1, Integer::sum);
        }
        for (int i : res) {
            System.out.print(i + " ");
        }
    }
}

LeetCode 2653. 滑动子数组的美丽值

先尝试了 固定滑动窗口+排序   结果超时了 时间复杂度应该是O（nlogn）吧....


package com.coedes.datastruct.hash.likou2653;

import java.util.ArrayList;
import java.util.Collections;


/**
 * @description：https://leetcode.cn/problems/sliding-subarray-beauty/description/
 * @author： wenLiu
 * @create： 2024/4/20 20:56
 */
public class Solution {
    public static void main(String[] args) {
//        nums = [1,-1,-3,-2,3], k = 3, x = 2
        int[] nums = {-3, 1, 2, -3, 0, -3};
        int k = 2;
        int x = 1;
        int[] ints = new Solution().getSubarrayBeauty(nums, k, x);
        for (int i : ints) {
            System.out.print(i + " ");
        }
    }

    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        ArrayList<Integer> list = new ArrayList<>();
        int indexOfRes = 0;
        for (int r = 0, l = 0; r < n; r++) {
            list.add(nums[r]);
            while (r - l + 1 > k) {
//                list.remove(l);
                list.remove(0);
                l++;
            }
            if (list.size() == k) {
                System.out.println(list.toString());
                ArrayList<Integer> tmpList = new ArrayList<>(list);
                Collections.sort(tmpList);
                //如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。
                res[indexOfRes++] = tmpList.get(x - 1) < 0 ? tmpList.get(x - 1) : 0;
            }
        }
        return res;
    }
}　

还是看大佬写的吧...

class Solution {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        final int BIAS = 50;
        var cnt = new int[BIAS * 2 + 1];
        int n = nums.length;
        for (int i = 0; i < k - 1; ++i) // 先往窗口内添加 k-1 个数
            ++cnt[nums[i] + BIAS];
        var ans = new int[n - k + 1];
        for (int i = k - 1; i < n; ++i) {
            ++cnt[nums[i] + BIAS]; // 进入窗口（保证窗口有恰好 k 个数）
            int left = x;
            for (int j = 0; j < BIAS; ++j) { // 暴力枚举负数范围 [-50,-1]
                left -= cnt[j];
                if (left <= 0) { // 找到美丽值
                    ans[i - k + 1] = j - BIAS;
                    break;
                }
            }
            --cnt[nums[i - k + 1] + BIAS]; // 离开窗口
        }
        return ans;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/sliding-subarray-beauty/solutions/2241294/hua-dong-chuang-kou-bao-li-mei-ju-by-end-9mvl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。