优于网上博客(原创):以LeetCode 219. Contains Duplicate II 为例说明为啥公司爱面动态规划


题目链接: https://leetcode.com/problems/ ... tion/
题意大概是,给一个数组和一个k,数组的任意两个下标i,j,问abs(i - j) <= k的范围内有木有重复的值。

这道题我第一个想法就是动态规划,AC完后去网上看有没有更好的解法,看了几个发现我这个解法最好,同时能展示动态规划的优势,所以写出来希望对大家有用,不足之处欢迎指正。

这道题目网上通用的解法是存一个<int, int>的map(见解法二),但如果用动态规划的解法,就可以在时间复杂度一样的条件下用<int, bool>的map,差距在哪呢?

差距在:我们把一个用大量int才能解决的问题变成了用同样数量bool就能解决。
int是4个字节,bool是一个字节,1M内存大约能放26万个int,但是可以放100多万个bool,假如有10亿个int(一个国家人口的id数),int会占用4G内存,而用bool的动态规划解法,将只占用1G内存,省了足足3G内存。现在漫天大数据的时代,这也许就是公司为啥爱面动态规划的原因之一了吧。

解法一:动态规划:

考虑一下,我第一次算的时候,是不是算nums[0,....k]这个子数组有没有重复,第二次呢,当前就是算nums[1....k+1]这个子数组有没有重复,依次循环.....

动态转移方程:nums_now[begin, end] = nums_last[last_bgein + 1, last_end + 1];

和网上的解法一样,我们每次用map存一个数是否出现过,那么我们其实只需要把nums_last的begin元素标记为没出现,再把nums的end+1元素添加进来判断就可以了:
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size() == 0 || k <= 0){
            return false;
        }

        map<int, bool> mp;
        int t = k;
        for (int i = 0; i < nums.size() && t >= 0; ++i){
            t--;
            if(mp[nums[i]] == false){
                mp[nums[i]] = true;
            }else{
                return true;
            }
        }
        
        t = 0;
        for (int i = k + 1; i < nums.size(); ++i){
            mp[nums[t++]] = false;
            if (mp[nums[i]] == false){
                mp[nums[i]] = true;
            }else{
                return true;
            }
        }
        return false;
    }
};


解法二(Java):
import java.util.HashMap;
import java.util.Map;

public class Solution {

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 输入条件判断
        if (nums == null || nums.length < 2 || k < 1) {
            return false;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {

            // 如果没有对应的key添加进去
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            }
            // 已经有对应的key-value对
            else {
                // 原来保存的值对应的下标,它一定小于现在的下标
                int value = map.get(nums[i]);
                if (i - value <= k) {
                    return true;
                }
                map.put(nums[i], i);
            }
        }
        return false;
    }
}
已邀请:

要回复问题请先登录注册

返回顶部