スライディングウィンドウアルゴリズム (C#)

数列 int[] arr が与えられるので、n 種類の値を含む最短の範囲を返せ
複数ある場合は arr の先頭に近い方を返すこと。
見つからない場合は null を返すこと。
制約：
1 ≦ arr.Length
1 ≦ n

という問題を愚直に実装するとこうなる……

		private Range_t Test01_e1(int[] arr, int n)
		{
			for (int w = n; w <= arr.Length; w++)
			{
				for (int s = 0; s + w <= arr.Length; s++)
				{
					HashSet<int> h = new HashSet<int>();

					for (int i = s; i < s + w; i++)
						h.Add(arr[i]);

					if (n <= h.Count)
						return new Range_t() { Start = s, End = s + w };
				}
			}
			return null;
		}

		// ----
		// ----
		// -- 以下共通 --

		private class Range_t
		{
			/// <summary>
			/// 開始位置(最初の要素のインデックス)
			/// </summary>
			public int Start;

			/// <summary>
			/// 終了位置(最後の要素のインデックス+1)
			/// </summary>
			public int End;

			/// <summary>
			/// 要素数
			/// </summary>
			public int Count
			{
				get
				{
					return this.End - this.Start;
				}
			}
		}

……のですが、arr の長さが 1,000,000 とかやたら長い場合はスライディングウィンドウで何とかする。
↓こんなん

		private Range_t Test01_e2(int[] arr, int n)
		{
			Dictionary<int, int> d = new Dictionary<int, int>();
			Range_t range = null;
			int l = 0;
			int r = 0;

			for (; ; )
			{
				for (; ; )
				{
					if (arr.Length <= r)
						return range;

					int k = arr[r++];

					if (d.ContainsKey(k))
						d[k]++;
					else
						d.Add(k, 1);

					if (n <= d.Count)
						break;
				}
				for (; ; )
				{
					int k = arr[l++];

					if (--d[k] == 0)
					{
						d.Remove(k);
						break;
					}
				}
				Range_t currRange = new Range_t() { Start = l - 1, End = r };

				if (range == null || range.Count > currRange.Count)
					range = currRange;
			}
		}

　
また似たようなやつで、

数列 int[] arr が与えられるので、値が重複しない最長の範囲を返せ
複数ある場合は arr の先頭に近い方を返すこと。
制約：
1 ≦ arr.Length

今度は最短じゃなくて最長。
これを愚直に実装すると、

		private Range_t Test02_e1(int[] arr)
		{
			for (int w = arr.Length; 2 <= w; w--)
			{
				for (int s = 0; s + w <= arr.Length; s++)
				{
					HashSet<int> h = new HashSet<int>();
					bool dupl = false;

					for (int i = s; i < s + w; i++)
					{
						int k = arr[i];

						if (h.Contains(k))
						{
							dupl = true;
							break;
						}
						h.Add(k);
					}
					if (!dupl)
						return new Range_t() { Start = s, End = s + w };
				}
			}
			return new Range_t() { Start = 0, End = 1 };
		}

これも長い arr の場合、同様にスライディングウィンドウで何とかする。
↓こんなん

		private Range_t Test02_e2(int[] arr)
		{
			Dictionary<int, int> d = new Dictionary<int, int>();
			Range_t range = null;
			int l = 0;
			int r = -1;

			for (; ; )
			{
				for (; ; )
				{
					if (arr.Length <= ++r)
						break;

					int k = arr[r];

					if (d.ContainsKey(k))
					{
						if (++d[k] == 2)
							break;
					}
					else
					{
						d.Add(k, 1);
					}
				}
				Range_t currRange = new Range_t() { Start = l, End = r };

				if (range == null || range.Count < currRange.Count)
					range = currRange;

				if (arr.Length <= r)
					return range;

				while (d[arr[l++]]-- != 2) ;
			}
		}

---

以下検証用

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Charlotte.Commons;

namespace Charlotte.Tests
{
	public class Test0009
	{
		private TimeSpan TotalTm1 = new TimeSpan(0L);
		private TimeSpan TotalTm2 = new TimeSpan(0L);

		public void Test01()
		{
			for (int c = 0; c < 10000; c++)
			{
				if (c % 100 == 0) ProcMain.WriteLog(string.Join(" / ", c, TotalTm1, TotalTm2)); // cout

				Test01_a();
			}
			ProcMain.WriteLog("OK! (TEST-0009-01)");
		}

		private void Test01_a()
		{
			Test01_b(10);
			Test01_b(30);
			Test01_b(100);
			Test01_b(300);
		}

		private void Test01_b(int arrScale)
		{
			Test01_c(arrScale, 10);
			Test01_c(arrScale, 20);
			Test01_c(arrScale, 100);
			Test01_c(arrScale, 300);
		}

		private void Test01_c(int arrScale, int elementKindScale)
		{
			Test01_d(arrScale, elementKindScale, 10);
			Test01_d(arrScale, elementKindScale, 30);
			Test01_d(arrScale, elementKindScale, 100);
			Test01_d(arrScale, elementKindScale, 300);
		}

		private void Test01_d(int arrScale, int elementKindScale, int requiredKindScale)
		{
			int arrLen = SCommon.CRandom.GetRange(1, arrScale);
			int elementKind = SCommon.CRandom.GetRange(1, elementKindScale);
			int requiredKind = SCommon.CRandom.GetRange(1, requiredKindScale);

			int elementMin = SCommon.CRandom.GetRange(-SCommon.IMAX / 2, SCommon.IMAX / 2); // rough range

			int[] arr = SCommon
				.Generate(arrLen, () => elementMin + SCommon.CRandom.GetInt(elementKind))
				.ToArray();

			DateTime stTm = DateTime.Now;
			Range_t ans1 = Test01_e1(arr, requiredKind);
			DateTime mdTm = DateTime.Now;
			Range_t ans2 = Test01_e2(arr, requiredKind);
			DateTime edTm = DateTime.Now;

			TimeSpan tm1 = mdTm - stTm;
			TimeSpan tm2 = edTm - mdTm;

			TotalTm1 += tm1;
			TotalTm2 += tm2;

			if (ans1 == null)
			{
				if (ans2 != null)
					throw null;
			}
			else
			{
				if (
					ans2 == null ||
					ans1.Start != ans2.Start ||
					ans1.End != ans2.End
					)
					throw null;
			}
		}

		private class Range_t
		{
			/// <summary>
			/// 開始位置(最初の要素のインデックス)
			/// </summary>
			public int Start;

			/// <summary>
			/// 終了位置(最後の要素のインデックス+1)
			/// </summary>
			public int End;

			/// <summary>
			/// 要素数
			/// </summary>
			public int Count
			{
				get
				{
					return this.End - this.Start;
				}
			}
		}

		// 乱数列が与えられるので、n種類の値を含む最短の範囲を返せ
		// 複数ある場合は乱数列の先頭に近い方を返すこと。
		// 見つからない場合は null を返すこと。
		// 制約：
		// 1 <= arr.Length
		// 1 <= n

		private Range_t Test01_e1(int[] arr, int n)
		{
			for (int w = n; w <= arr.Length; w++)
			{
				for (int s = 0; s + w <= arr.Length; s++)
				{
					HashSet<int> h = new HashSet<int>();

					for (int i = s; i < s + w; i++)
						h.Add(arr[i]);

					if (n <= h.Count)
						return new Range_t() { Start = s, End = s + w };
				}
			}
			return null;
		}

		private Range_t Test01_e2(int[] arr, int n)
		{
			Dictionary<int, int> d = new Dictionary<int, int>();
			Range_t range = null;
			int l = 0;
			int r = 0;

			for (; ; )
			{
				for (; ; )
				{
					if (arr.Length <= r)
						return range;

					int k = arr[r++];

					if (d.ContainsKey(k))
						d[k]++;
					else
						d.Add(k, 1);

					if (n <= d.Count)
						break;
				}
				for (; ; )
				{
					int k = arr[l++];

					if (--d[k] == 0)
					{
						d.Remove(k);
						break;
					}
				}
				Range_t currRange = new Range_t() { Start = l - 1, End = r };

				if (range == null || range.Count > currRange.Count)
					range = currRange;
			}
		}

		public void Test02()
		{
			for (int c = 0; c < 10000; c++)
			{
				if (c % 100 == 0) ProcMain.WriteLog(string.Join(" / ", c, TotalTm1, TotalTm2)); // cout

				Test02_a();
			}
			ProcMain.WriteLog("OK! (TEST-0009-02)");
		}

		private void Test02_a()
		{
			Test02_b(10);
			Test02_b(30);
			Test02_b(100);
			Test02_b(300);
		}

		private void Test02_b(int arrScale)
		{
			Test02_c(arrScale, 10);
			Test02_c(arrScale, 20);
			Test02_c(arrScale, 100);
			Test02_c(arrScale, 300);
		}

		private void Test02_c(int arrScale, int elementKindScale)
		{
			int arrLen = SCommon.CRandom.GetRange(1, arrScale);
			int elementKind = SCommon.CRandom.GetRange(1, elementKindScale);

			int elementMin = SCommon.CRandom.GetRange(-SCommon.IMAX / 2, SCommon.IMAX / 2); // rough range

			int[] arr = SCommon
				.Generate(arrLen, () => elementMin + SCommon.CRandom.GetInt(elementKind))
				.ToArray();

			DateTime stTm = DateTime.Now;
			Range_t ans1 = Test02_e1(arr);
			DateTime mdTm = DateTime.Now;
			Range_t ans2 = Test02_e2(arr);
			DateTime edTm = DateTime.Now;

			TimeSpan tm1 = mdTm - stTm;
			TimeSpan tm2 = edTm - mdTm;

			TotalTm1 += tm1;
			TotalTm2 += tm2;

			if (
				ans1 == null ||
				ans2 == null ||
				ans1.Start != ans2.Start ||
				ans1.End != ans2.End
				)
				throw null;
		}

		// 乱数列が与えられるので、値が重複しない最長の範囲を返せ
		// 複数ある場合は乱数列の先頭に近い方を返すこと。
		// 制約：
		// 1 <= arr.Length

		private Range_t Test02_e1(int[] arr)
		{
			for (int w = arr.Length; 2 <= w; w--)
			{
				for (int s = 0; s + w <= arr.Length; s++)
				{
					HashSet<int> h = new HashSet<int>();
					bool dupl = false;

					for (int i = s; i < s + w; i++)
					{
						int k = arr[i];

						if (h.Contains(k))
						{
							dupl = true;
							break;
						}
						h.Add(k);
					}
					if (!dupl)
						return new Range_t() { Start = s, End = s + w };
				}
			}
			return new Range_t() { Start = 0, End = 1 };
		}

		private Range_t Test02_e2(int[] arr)
		{
			Dictionary<int, int> d = new Dictionary<int, int>();
			Range_t range = null;
			int l = 0;
			int r = -1;

			for (; ; )
			{
				for (; ; )
				{
					if (arr.Length <= ++r)
						break;

					int k = arr[r];

					if (d.ContainsKey(k))
					{
						if (++d[k] == 2)
							break;
					}
					else
					{
						d.Add(k, 1);
					}
				}
				Range_t currRange = new Range_t() { Start = l, End = r };

				if (range == null || range.Count < currRange.Count)
					range = currRange;

				if (arr.Length <= r)
					return range;

				while (d[arr[l++]]-- != 2) ;
			}
		}
	}
}

2024.9.24　訂正：ウィンドウスライディング ⇒ スライディングウィンドウ