LeetCode 220. Contains Duplicate III – 柳婼 の blog
分析：建立一个map，对应的是元素的值到元素的下标的映射。指针i将nums数组从头遍历到尾，j指针一开始指向0。i向右走的时候如果i和j之差大于k，且m中有nums[j]，就将nums[j]从m中移除，且j向前走一步～这样就保证了m中所有的元素满足第一个条件：i和j的差的绝对值不超过k～
接下来考虑nums[i]和nums[j]的差的绝对值不超过t，abs(num[i] – nums[j]) <= t 则 nums[j]的最小可能满足条件的值为>=nums[i] – t的，所以使用map中的lower_bound，寻找第一个大于等于nums[i] – t的地方，找到后标记为a，此时的a只是取到了可能满足的最小的a，但(a – nums[i])不一定满足，所以检验a是否存在于map中且是否abs(a->first – nums[i]) <= t。如果都满足说明可以return true～
为什么要循环的最后写map的插入呢，因为比较的是i之前的所有元素～为了防止找到的是nums[i]本身，然后让nums[i]自己本身和自己比较差值了，这样结果就不对了～
如果到最后都没有能够return true，则return false～
Read full article from LeetCode 220. Contains Duplicate III – 柳婼 の blog
No comments:
Post a Comment