算法竞赛入门：UVA11572 Unique Snowflakes

UVA11572 Unique Snowflakes

题目大意：给定 n 个数，找尽量长的一个连续子序列，使该子序列没有重复的元素。

可以使用双指针法解决问题，移动指针保证两个指针形成的子区间没有重复的元素，C++ 可以用到 STL set ，Java 语言可以使用 HashSet 存储元素（当然用哈希表代替也可以）。指针 i 指向区间左端点，指针 j 指向区间右端点，j 不断尝试向右侧扩展区间，将新数加入到 Set 中，如果发现元素有重复，则移动 i 指针缩短区间长度。

代码实现：

import java.util.*; class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n,t; t=sc.nextInt(); for(int T=0;T<t;T++) { n=sc.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } Set<Integer> S=new HashSet<>(); int i=0,j=0,ans=0; for( ;j<n;j++){ while(i<j&&S.contains(a[j])){ S.remove(a[i]); i++; } S.add(a[j]); ans=Math.max(ans,j-i+1); } System.out.println(ans); } } }

实际上，本题还有其他解法，例如二分法，map 等。二分法的时间性能与双指针法差别不大，感兴趣的朋友可以用其他解法做出。

双指针法本身并不难理解，也比较容易编程实现，不管是面试题还是算法竞赛题目中考察的都比较多。这种算法的编程的套路比较固定，对于这类题型，只需要分析清楚题目的应用场景，选择适合的做法即可。