DEV Community
·
打印所有和为给定值的唯一数对
内容提要
给定一个整数数组和一个数字'sum'，打印出数组中所有和为'sum'的唯一对。方法一是对数组进行排序，将重复的元素放在一起。使用两个指针left和right，检查三种情况：case-1 arr[left]+arr[right]==sum，打印出有效的对并移动指针。case-2 arr[left]+arr[right]<sum，移动left指针。case-3 arr[left]+arr[right]>sum，移动right指针。方法二是使用哈希表，遍历元素，对于每个元素找到其补数，并检查是否之前已经出现过。如果之前出现过，有两种情况：case-1 元素和补数相同，检查频率。如果频率为1，则打印出这对。如果频率大于1，则跳过。case-2 如果当前元素和补数不同，检查补数是否存在于哈希表中。如果存在，表示之前已经遇到过这个补数。只有在第一次处理当前元素时才打印出这对。如果之前没有出现过，则继续搜索下一个元素。
关键要点
-
给定一个整数数组和一个数字'sum'，打印出数组中所有和为'sum'的唯一对。
-
方法一：对数组进行排序，将重复的元素放在一起，使用两个指针left和right检查三种情况。
-
情况1：arr[left] + arr[right] == sum，打印有效对并移动指针。
-
情况2：arr[left] + arr[right] < sum，移动left指针以获取更大的值。
-
情况3：arr[left] + arr[right] > sum，移动right指针以获取更小的值。
-
时间复杂度为O(N) + O(NlogN)。
-
方法二：使用哈希表，遍历元素，找到其补数并检查是否之前出现过。
-
情况1：元素和补数相同，检查频率，如果频率为1则打印对，频率大于1则跳过。
-
情况2：如果当前元素和补数不同，检查补数是否存在于哈希表中。
-
避免重复对的打印，只有在第一次处理当前元素时才打印对。
-
时间复杂度为O(N)，空间复杂度为O(N)。
延伸问答
如何找到数组中和为给定值的唯一数对？
可以通过对数组排序并使用两个指针的方法，或者使用哈希表来查找和为给定值的唯一数对。
使用两个指针的方法是如何工作的？
首先对数组排序，然后使用左指针和右指针检查三种情况：相等、左指针值小于和、右指针值大于和，并相应移动指针。
哈希表方法如何避免重复数对的打印？
在哈希表方法中，只有在第一次处理当前元素时才打印数对，并检查元素和补数的频率以避免重复。
这两种方法的时间复杂度分别是多少？
双指针方法的时间复杂度为O(N) + O(NlogN)，而哈希表方法的时间复杂度为O(N)。
在使用双指针方法时，如何处理重复元素？
在找到有效对后，需要跳过重复的元素，确保只打印第一次出现的数对。
如何实现哈希表方法来查找数对？
创建一个哈希表存储元素及其频率，遍历数组，检查每个元素的补数是否存在于哈希表中，并根据频率决定是否打印数对。
