算法篇02、数组相关算法--哈希表、优先队列、集合、滑动窗口、双指针、二分搜索等

作者: 稀土掘金  更新时间:2021-05-04 11:39:20  原文链接


本篇涉及的题目都是数组相关的,解法主要包括哈希表、集合、优先队列、滑动窗口、双指针、二分搜索等技术;

1、leetcode349--两个数组的交集

给定两个数组,编写一个函数来计算它们的交集。 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

题目要求是求两个数组的交集,并且不能有重复元素,因此我们可以借助HashSet来解决;

题解如下所示,首先将nums1数组中的元素放入HashSet1,这样就自动将数组1中的元素去重了,然后再新建一个HashSet2,依次遍历数组2,如果HashSet1中存在遍历到的元素,就将元素放入HashSet2,这样HashSet2中的元素就是最后需要的结果;

//leetcode349两个数组的交集
//不可重复
public int[] intersection(int[] nums1, int[] nums2) {
    HashSet<Integer> num1Set = new HashSet<>();
    for (int i = 0; i < nums1.length; i++) {
        num1Set.add(nums1[i]);
    }

    HashSet<Integer> res = new HashSet<>();
    for (int i = 0; i < nums2.length; i++) {
        if (num1Set.contains(nums2[i])){
            res.add(nums2[i]);
        }
    }
    int[] result = new int[res.size()];
    Object[] objects = res.toArray();
    for (int i = 0; i < result.length; i++) {
        result[i] = (int) objects[i];
    }
    return result;
}

2、leetcode350--两个数组的交集II

给定两个数组,编写一个函数来计算它们的交集。 输出结果中每个元素出现的次数,应与元素在两个数组中出现次数的最小值一致。 我们可以不考虑输出结果的顺序。

本题跟349唯一的不同是可以出现重复的元素,出现次数与两个数组中出现次数的最小值一致;

题解如下所示,我们可以借助HashMap来解决问题;先使用HashMap保存数组1中的元素及其出现的次数,然后遍历一遍数组2,如果HashMap中存在遍历到的元素,就取出放到结果集中,接着把HashMap中此元素的次数减一,如果次数变为0了,说明此元素不需要了,就从HashMap中移除;这样遍历完数组2,结果集就是我们需要的结果了;

//leetcode350两个数组的交集II
//可重复,以出现最少次数的数组为准
public int[] intersect(int[] nums1, int[] nums2) {
    HashMap<Integer,Integer> nums1Map = new HashMap<>();
    for (int i = 0; i < nums1.length; i++) {
        nums1Map.put(nums1[i],nums1Map.getOrDefault(nums1[i],0) + 1);
    }

    ArrayList<Integer> res = new ArrayList<>();
    for (int i = 0; i < nums2.length; i++) {
        if (nums1Map.containsKey(nums2[i])){
            res.add(nums2[i]);
            nums1Map.put(nums2[i],nums1Map.get(nums2[i])-1);
            if (nums1Map.get(nums2[i]) == 0){
                nums1Map.remove(nums2[i]);
            }
        }
    }
    Object[] objects = res.toArray();
    int[] result = new int[objects.length];
    for (int i = 0; i < objects.length; i++) {
        result[i] = (int) objects[i];
    }
    return result;
}

3、leetcode209--长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

本题是一道典型的滑动窗口可以解决的类型的题目,解法如下所示;

滑动窗口的思想就是一直维护一个[l...r]的滑动窗口,使窗口中元素符合要求,然后根据窗口不断更新最终的结果;本题就是维护窗口内的元素和大于等于target,如果窗口长度比当前记录的长度还小,就更新为此窗口长度;

//leetcode 209 长度最小的子数组
public int minSubArrayLen(int target, int[] nums) {
    //维持一个[l...r]的滑动窗口
    int l = 0;
    int r = -1;
    int res = Integer.MAX_VALUE;
    int sum = 0;
    while (r < nums.length - 1) {
        if (sum < target) {
            r++;
            sum += nums[r];
        }
        while (sum >= target) {
            if (r - l + 1 < res) {
                res = r - l + 1;
            }
            //此处是开始犯的错误,应该是先减nums[l],然后再进行l++的操作!!!!!
//                l++;
//                sum -= nums[l];

            sum -= nums[l];
            l++;
        }
    }
    return res == Integer.MAX_VALUE ? 0 : res;
}

4、leetcode283--移动零到数组末尾

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

题解如下所示,这题我们可以借助ArrayList,先通过ArrayList保存原数组中非零元素的顺序,然后将此ArrayList填充到原数组前ArrayList.size()个位置的元素,那么原数组剩余位置的元素肯定都是0了,此时用0填充剩余位置的数据即可;

//leetcode 283 移动零到数组末尾
public void moveZeroes(int[] nums) {
    ArrayList<Integer> nonZeroElements = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0){
            nonZeroElements.add(nums[i]);
        }
    }
    for (int i = 0; i < nonZeroElements.size(); i++) {
        nums[i] = nonZeroElements.get(i);
    }
    for (int i = nonZeroElements.size(); i < nums.length; i++) {
        nums[i] = 0;
    }
}

5、leetcode167--两数之和

给定一个已按照 升序排列 的整数数组 numbers,请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。

题解如下所示,本题是一道典型的可以使用左右双指针解决的类型的问题;

定义左右两个指针位于数组的头和尾,然后将两个指针处的元素相加,因为数组是有序的,如果和小于target,就将左指针右移一位;如果和大于target,就将右指针左移一位;如果和等于target,说明找到答案,直接返回即可;

//leetcode 167 两数之和 数组有序
//双指针
public int[] twoSum(int[] numbers, int target) {
    int l = 0;
    int r = numbers.length -1;
    int[] res = new int[2];
    while (l < r){
        if (numbers[l] + numbers[r] < target){
            l++;
        } else if (numbers[l] + numbers[r] >target) {
            r--;
        }else {
            res[0] = l+1;
            res[1] = r+1;
            return res;
        }
    }
    return res;
}

6、leetcode01--两数之和

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

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

解法一 暴力解法 可以在一个两层嵌套的for循环中遍历数组,直到找到两个数相加等于target;因为是一个双层嵌套的for循环,所以时间复杂度是O(n^2)级别的;

//leetcode01 两数之和 数组无序 暴力解法时间复杂度O(n^2)
public int[] twoSum3(int[] nums, int target) {
    int[] res = new int[2];
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i+1; j < nums.length; j++) {
            if (nums[j] + nums[i] == target){
                res[0] = i;
                res[1] = j;
            }
        }
    }
    return res;
}

解法二 借助HashMap 我们可以借助HashMap保存数组中的元素值和索引,然后遍历数组,去HashMap中查找是否存在 target-遍历到的当前值,如果存在说明两个数的和为target,此时直接把HashMap中保存的索引和遍历到的当前值的索引返回即可;并且这个过程只需要遍历一遍数组即可,是不是非常巧妙~ 时间复杂度是O(n)级别的;

//leetcode01 两数之和 数组无序 借助hashmap记录索引,时间复杂度O(n)
public int[] twoSum2(int[] nums, int target) {
    int[] res = new int[2];
    HashMap<Integer,Integer> hashMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (hashMap.containsKey(target - nums[i])){
            res[0] = hashMap.get(target - nums[i]);
            res[1] = i;
        }
        hashMap.put(nums[i],i);
    }
    return res;
}

7、leetcode804--唯一的摩尔斯密码

国际摩尔斯密码定义一种标准编码方式,将每个字母对应于一个由一系列点和短线组成的字符串, 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。

为了方便,所有26个英文字母对应摩尔斯密码表如下:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

给定一个单词列表,每个单词可以写成每个字母对应摩尔斯密码的组合。例如,"cab" 可以写成 "-.-..--...",(即 "-.-." + ".-" + "-..." 字符串的结合)。我们将这样一个连接过程称作单词翻译。

返回我们可以获得所有词不同单词翻译的数量。

题解如下所示,把数组中的所有单词都翻译成莫尔斯密码,然后保存到HashSet中,最后返回HashSet的size即可,因为HashSet可以自动去重;

//leetcode 804 唯一的摩尔斯密码
public int uniqueMorseRepresentations(String[] words) {
    HashSet<String> set = new HashSet<>();
    for (String word : words) {
        String morseCode = transformWordToMorseCode(word);
        set.add(morseCode);
    }
    return set.size();
}

private String transformWordToMorseCode(String word) {
    String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    char[] chars = word.toCharArray();
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < chars.length; i++) {
        builder.append(morse[chars[i] - 'a']);
    }
    return builder.toString();
}

8、leetcode75--颜色分类

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

题解如下所示,我们可以借助快速排序中三路快排的思想解决这个问题;当元素为0时放在左边,当元素为1时放在中间,当元素为2时放在右边,最后遍历完也就排完序了,时间复杂度是O(n)级别的;

//leetcode 75 颜色排序,借助三路快排思想
public void sortColors(int[] nums) {
    int l = 0;
    int r = nums.length - 1;
    int m = l -1;
    int n = r + 1;
    //for循环走完后 [l...m]表示0;(m...n)表示1;[n...r]表示2;
    for (int i = 0; i < n; ) {
        if (nums[i] == 0){
            swap(nums,m+1,i);
            m++;
            i++;
        }else if (nums[i] == 2){
            swap(nums,n-1,i);
            n--;
        }else {
            i++;
        }
    }
}

//交换nums数组中a、b位置的元素
private void swap(int[] nums, int a, int b) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}

9、leetcode347--前K个高频元素

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

题解如下所示,本题很好的结合了哈希表和优先队列;我们首先遍历一边数组,将元素及其出现的次数保存到HashMap中;然后新建一个优先队列,使用HashMap的value值相减作为比较器,这样就保证了数的频率越高,其优先级越低;最后遍历一遍HashMap,在优先队列中元素小于K时直接放入,否则就比较队列首的元素和遍历到的元素,如果遍历到的元素的频率比队列首的元素的频率还高,就把队列首元素出队,让遍历到的元素入队;因为队列首的元素始终是优先队列中频率最低的那个;

因为就遍历了两遍数组,所以时间复杂度是O(2n),忽略常数,时间复杂度就是O(n)级别的;

//leetcode347 前K个高频元素
public int[] topKFrequent(int[] nums, int k) {
    HashMap<Integer,Integer> hashMap = new HashMap<>();
    for (int num : nums) {
        hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
    }
    PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            return hashMap.get(a) - hashMap.get(b);
        }
    });

    for (Integer key : hashMap.keySet()) {
        if (queue.size() < k){
            queue.add(key);
        }else if (hashMap.get(key) > hashMap.get(queue.peek())) {
            queue.remove();
            queue.add(key);
        }
    }

    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = queue.remove();
    }
    return res;
}

10、leetcode454--四数之和为0的元组

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间,最终结果不会超过 2^31 - 1 。

解法一 暴力解法

直接使用四层嵌套for循环遍历数组,不过此种方式时间复杂度为O(n^4)级别的,性能太差;

//leetcode454 四数之和为0的元组
//暴力解法四重循环,时间复杂度O(n^4),爆炸,无法忍受
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    int res = 0;
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            for (int k = 0; k < nums3.length; k++) {
                for (int l = 0; l < nums4.length; l++) {
                    if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
                        res ++;
                    }
                }
            }
        }
    }
    return res;
}

解法二 借助哈希表

首先使用两层嵌套for循环遍历前两个数组,将前两个数组所有和及其出现的次数保存到HashMap中;然后再使用一个双层嵌套的for循环遍历后两个数组,在HashMap中找这两个数组元素和的相反数即可,主要找到之后加的是HashMap的value值;

//借助hashmap,时间复杂度降低为O(n^2)
public int fourSumCount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    //key代表nums1和nums2元素相加的和,value代表和的个数
    HashMap<Integer,Integer> hashMap = new HashMap<>();
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            int sum = nums1[i] + nums2[j];
            hashMap.put(sum,hashMap.getOrDefault(sum,0) + 1);
        }
    }
    int res = 0;
    for (int i = 0; i < nums3.length; i++) {
        for (int j = 0; j < nums4.length; j++) {
            int sum = nums3[i] + nums4[j];
            if (hashMap.containsKey(-sum)){
                res+=hashMap.get(-sum);
            }
        }
    }
    return res;
}

11、leetcode704--有序数组的二分搜索

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

有序数组的二分搜索是比较经典的算法问题,因为数组是有序的,每次去数组中间查找,如果中间的数比target还要小,就去右边子数组查找;如果中间的数比target还要大,就去左边子数组查找;如果等于target,直接返回;这样每次查找后都减少一半的元素,时间复杂度是O(logn)级别的;

//leetcode 704 有序数组的二分搜索
public int search(int[] nums, int target) {
    int l = 0;
    int r = nums.length - 1;
    while (l <= r){
        int mid = l + (r - l) / 2;
        if (nums[mid] < target){
            l = mid + 1;
        }else if (nums[mid] > target){
            r = mid - 1;
        }else {
            return mid;
        }
    }
    return -1;
}

12、leetcode217--存在重复元素

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

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

题解如下,本题非常简单,直接借助HashSet不能存放重复元素的性质即可,时间复杂度为O(n)级别;

//leetcode 217 存在重复元素
public boolean containsDuplicate(int[] nums) {
    HashSet<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        if (set.contains(nums[i])){
            return true;
        }
        set.add(nums[i]);
    }

    return false;
}

13、leetcode219--存在重复元素II

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的 绝对值 至多为 k。

题解如下所示,本题借助HashMap即可,将数组中元素的值以及索引保存到HashMap中,遍历数组,如果HashMap中存在遍历到的元素,并且索引值相差小于等于k,直接返回true即可;如果遍历完还是没有满足的,返回false;

本题这个过程还巧妙在只需要遍历一遍数组,时间复杂度是O(n)级别的;

//leetcode 219 存在重复元素II
public boolean containsNearbyDuplicate(int[] nums, int k) {
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        if (hashMap.containsKey(nums[i]) && Math.abs(i - hashMap.get(nums[i])) <= k) {
            return true;
        }
        hashMap.put(nums[i], i);
    }
    return false;
}

14、leetcode220--存在重复元素III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j,使得 abs(nums[i] - nums[j]) <= t ,同时又满足 abs(i - j) <= k 。

如果存在则返回 true,不存在返回 false。

首先我们需要知道两个api什么意思; TreeSet treeSet = new TreeSet<>(); treeSet.ceiling(6); ceiling表示treeSet中比6大的最小的那个值; treeSet.floor(6); floor表示treeSet中比6小的最大的那个值;

题解如下所示,本题就借助了TreeSet元素的有序性,因为其底层实现是红黑树,因此可以保证元素的有序性;

其中这一句 treeSet.ceiling((long) nums[i] - (long) t) <= (long) nums[i] + (long) t 就表示满足了 abs(nums[i] - nums[j]) <= t ;而当 treeSet.size() == k + 1 时就将最先方法的那个元素移除,这就满足了 abs(i - j) <= k ;这样我们借助TreeSet就满足了这两个条件;

本题只遍历了一遍数组,时间复杂度是O(n)级别的;

//leetcode 220 存在重复元素III
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    TreeSet<Long> treeSet = new TreeSet<>();
    for (int i = 0; i < nums.length; i++) {

        if (treeSet.ceiling((long) nums[i] - (long) t) != null && 
            treeSet.ceiling((long) nums[i] - (long) t) <= (long) nums[i] + (long) t) {
            return true;
        }
        treeSet.add((long) nums[i]);
        if (treeSet.size() == k + 1) {
            treeSet.remove((long) nums[i - k]);
        }
    }
    return false;
}

题目来源出处

来源:力扣(LeetCode) 链接: leetcode-cn.com/problemset/… 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。