Leetcode：219

1，题目

2，思路

第一种就是简单的暴力比对当时过年没细想

第二种：

• 用Map的特性key唯一，把数组的值作为Map的key值
• 我们每加载一个元素都会去判断这个元素在Map里面存在与否
• 如果存在进行第二个判断条件abs(i-j)<=k,条件
  • 符合直接true
  • 不符合就让在map中存在的元素被新元素覆盖即可，这样能确保后续判断有效，循环结束则false
• 第二种无论是在时间复杂度还是空间复杂度上都要比第一种更加优解

3，代码

import java.util.HashMap;

public class Leetcode219 {
    public static void main(String[] args) {
        System.out.println(new Solution219().containsNearbyDuplicate(new int[]{1, 2, 3, 1}, 3));
    }
}

class Solution219 {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        //return fun1(nums, k);//方法一：暴力
        return fun2(nums, k);//方法二：哈希表查找
    }

    public boolean fun1(int[] nums, int k) {
        int temp = k + 1;
        for (int i = 0; i < nums.length - 1; i++) {
            int index = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                int end = nums[j];
                if (index == end && Math.abs(i - j) <= k) {
                    return true;
                } else if (Math.abs(i - j) > k) {
                    break;
                }
            }
        }
        return false;
    }

    public boolean fun2(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();//建立哈希表

        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);//值为key这样值就是唯一的
            } else {
                int num = map.get(nums[i]);//获取题目中的i
                if (Math.abs(num - i) <= k) {
                    return true;
                } else {
                    map.put(nums[i], i);//否则覆盖
                }
            }
        }
        return false;
    }
}