元素中有重复元素吗？（2）

2019-02-22

题目

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

示例1：

1 2	输入: nums = [1,2,3,1], k = 3 输出: true

示例2：

1 2	输入: nums = [1,0,1,1], k = 1 输出: true

示例3：

1 2	输入: nums = [1,2,3,1,2,3], k = 2 输出: false

解法1：暴力法

双重遍历，依次比较查找，时间复杂度为O(n^2)。

BOOL checkTheSameNumberWithSpecificIndex1(NSArray<NSNumber *> *nums, NSInteger target) {
    if (nums.count <= 1) {
        return NO;
    }
    
    for (NSInteger i = 0; i < nums.count; i++) {
        // 当前数值
        NSInteger currentValue = [nums[i] integerValue];
        // 在依次查看之后的数据值是否相同
        for (NSInteger j = i + 1; j < nums.count; j++) {
            NSInteger nextValue = [nums[j] integerValue];
            if (currentValue == nextValue) {
                // 索引差是否符合要求
                if (labs(j - i) <= target) {
                    return YES;
                }
            }
        }
    }
    
    return NO;
}

解法2：哈希表

利用哈希表（OC中使用NSDictionary对象）的快速查找降低了复杂度，同时进行比较并更新。时间复杂度降低为O(n)。

BOOL checkTheSameNumberWithSpecificIndex2(NSArray<NSNumber *> *nums, NSInteger target) {
    if (nums.count <= 1) {
        return NO;
    }
    
    // 插入到哈希表中，同时检查：如果数值对应的key已经存在，则使用其索引与当前索引进行比较。符合要求则返回；不符合则插入新索引，继续向后检查
    NSMutableDictionary *hashTable = [[NSMutableDictionary alloc] initWithCapacity:10];
    
    for (NSInteger index = 0; index < nums.count; index++) {
        NSNumber *currentItem = nums[index];
        NSNumber *indexItem = hashTable[currentItem];
        if (!indexItem) {
            // 不存在，插入（key为数据值，value为索引）
            hashTable[currentItem] = @(index);
        } else {
            // 存在，取出value索引值，进行比较
            if(labs(indexItem.integerValue - index) <= target) {
                // 符合要求
                return YES;
            } else {
                // 不符合，更新此索引值
                hashTable[currentItem] = @(index);
            }
        }
    }
    
    return NO;
}