leetcode 220: Contains Duplicate III - 西施豆腐渣 - CSDN博客

leetcode 220: Contains Duplicate III - 西施豆腐渣 - CSDN博客

Contains Duplicate III

Total Accepted: 633 Total Submissions: 4437

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

[思路]

维持一个长度为k的window, 每次检查新的值是否与原来窗口中的所有值的差值有小于等于t的. 如果用两个for循环会超时O(nk). 使用treeset( backed by binary search tree) 的subSet函数,可以快速搜索. 复杂度为 O(n logk)

Read full article from leetcode 220: Contains Duplicate III - 西施豆腐渣 - CSDN博客