问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3716 访问。
给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.
注意:
数对 (i, j) 和数对 (j, i) 被算作同一数对。
数组的长度不超过10,000。
所有输入的整数的范围在 [-1e7, 1e7]。
Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.
Note:
The pairs (i, j) and (j, i) count as the same pair.
The length of the array won't exceed 10,000.
All the integers in the given input belong to the range: [-1e7, 1e7].
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3716 访问。
public class Program {
public static void Main(string[] args) {
int[] nums = null;
nums = new int[] { 3, 1, 4, 1, 5 };
var res = FindPairs(nums, 2);
Console.WriteLine(res);
Console.ReadKey();
}
private static int FindPairs(int[] nums, int k) {
if(k < 0) return 0;
var set1 = new HashSet<int>();
var set2 = new HashSet<int>();
for(int i = 0; i < nums.Length; i++) {
//包含+k时直接添加到set2
if(set1.Contains(nums[i] + k)) {
set2.Add(nums[i]);
}
//包含-k时直接添加到set2
if(set1.Contains(nums[i] - k)) {
set2.Add(nums[i] - k);
}
//把所有值存入set1
set1.Add(nums[i]);
}
//返回2中的数量即为结果
return set2.Count();
}
}以上给出1种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3716 访问。
2分析：
显而易见，以上算法的时间复杂度为： 。