Given a list of integers nums, return the length of the longest contiguous sublist where all its elements are distinct.
Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [5, 1, 3, 5, 2, 3, 4, 1]
Output
5
Explanation
The longest list of distinct elements is [5, 2, 3, 4, 1].Hints:
Could using two pointers to represent a sliding window help?
Two Pointer + Sliding Window to Compute the Longest Distinct SubList
We can use two pointer to form a sliding window. And use a hash map to count numbers in the window. If there are duplicate numbers in the window, we move the left pointer (shrink the window), otherwise we move the right pointer (extend the window).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | int longestDistinctSublist(vector<int>& nums) { int n = static_cast<int>(nums.size()); int L = 0, R = 0; int ans = 0; unordered_map<int, int> data; while (R < n) { data[nums[R]] ++; while (data.size() != R - L + 1) { data[nums[L]] --; if (data[nums[L]] == 0) { data.erase(nums[L]); } L ++; } ans = max(ans, R - L + 1); R ++; } return ans; } |
int longestDistinctSublist(vector<int>& nums) {
int n = static_cast<int>(nums.size());
int L = 0, R = 0;
int ans = 0;
unordered_map<int, int> data;
while (R < n) {
data[nums[R]] ++;
while (data.size() != R - L + 1) {
data[nums[L]] --;
if (data[nums[L]] == 0) {
data.erase(nums[L]);
}
L ++;
}
ans = max(ans, R - L + 1);
R ++;
}
return ans;
}Time complexity is O(N) and space complexity is O(N) where N is the number of numbers in the list.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Implement the String.Find Method in Python
Next Post: Teaching Kids Programming - Implement the Counter method in Python
