0532.数组中的数对 K-diff Pairs in an Array

问题描述

这是一个查找问题, 先思考一下处理查找问题的常用手段:

  • 哈稀表或者 HashSet
  • BitSet
  • 排序后二分查找
  • 排序后快慢型双指针遍历

哈稀表 Hash Table

使用哈稀表 HashMap 来统计整数值及其次数; 用集合 HashSet 来存放的有序数对, 并去掉重复的.

hash-table

这种方法可以支持无序数组.

#![allow(unused)]
fn main() {
// 哈稀表来计数
pub fn find_pairs1(nums: Vec<i32>, k: i32) -> i32 {
    assert!(!nums.is_empty());

    let mut map = HashMap::new();
    for num in &nums {
        map.entry(num).and_modify(|count| *count += 1).or_insert(1);
    }

    // 使用集合来去重.
    let mut set = HashSet::new();
    for &num in &nums {
        // k = diff - num;
        // diff1 >= num
        let diff1 = num + k;
        if let Some(count) = map.get(&diff1) {
            if (diff1 > num) || ((diff1 == num) && (*count > 1)) {
                set.insert(vec![num, diff1]);
            }
        }

        // k = num - diff;
        // diff2 <= num
        let diff2 = num - k;
        if let Some(count) = map.get(&diff2) {
            if diff2 < num {
                set.insert(vec![diff2, num]);
            } else if (diff2 == num) && (*count > 1) {
                set.insert(vec![num, diff2]);
            }
        }
    }

    set.len() as i32
}
}

基本的思路是:

  • 先给数组排序
  • 开始遍历数组
  • 根据题目条件, 确定目标的元素的值; 使用二分查找法搜索目标元素
  • 再根据要求, 判断目标元素是否合适, 比如两者索引值不能相同
#![allow(unused)]
fn main() {
// 排序后二分查找, 不使用额外内存. 根据 k == 0 做优化
pub fn find_pairs5(nums: Vec<i32>, k: i32) -> i32 {
    assert!(!nums.is_empty());

    // 先排序
    let mut nums = nums;
    nums.sort();
    let mut count = 0;
    let mut fast = 0;

    if k == 0 {
        let len = nums.len();

        // 遍历数组
        while fast < len {
            let curr_val = nums[fast];
            // 只保留两个重复元素, 跳过其它的.
            if fast + 1 < len && curr_val == nums[fast + 1] {
                count += 1;
                fast += 1;
            }
            while fast + 1 < len && curr_val == nums[fast + 1] {
                fast += 1;
            }

            // 指针向前走一步
            fast += 1;
        }
    } else {
        // 去掉重复元素
        nums.dedup();
        let len = nums.len();

        // 遍历数组
        while fast < len {
            let curr_val = nums[fast];
            let expected_val = curr_val + k;
            // 使用二分查找法在后面的元素里搜索 `expected_val`.
            if fast + 1 < len && nums[fast + 1..].binary_search(&expected_val).is_ok() {
                count += 1;
            }

            // 指针向前走一步
            fast += 1;
        }
    }

    count
}
}

快慢型双指针 Fast-Slow Two Pointers

这个方法的效率是最高的, 也最节省内存.

解决问题之前依然要先给数组排序.

fast-slow two-pointers

这个题目中, 双指针的命中条件是 nums[fast] - nums[slow] = k;, 只需要围绕这个核心条件做判断即可.

#![allow(unused)]
fn main() {
// 快慢型双指针
pub fn find_pairs6(nums: Vec<i32>, k: i32) -> i32 {
    let len = nums.len();
    if len <= 1 {
        return 0;
    }

    let mut nums = nums;
    // 先排序
    nums.sort();

    // 初始化两个指针, 两个指针不能重复.
    let mut fast = 1;
    let mut slow = 0;
    let mut count = 0;

    // 遍历整个数组.
    while fast < len {
        // 两个指针不能重复, 因为题目要求: `i != j`.
        if fast == slow {
            fast += 1;
            continue;
        }

        match (nums[fast] - nums[slow]).cmp(&k) {
            Ordering::Equal => {
                count += 1;
                let curr_slow = nums[slow];
                let curr_fast = nums[fast];

                // 跳过重复元素
                while slow < len && curr_slow == nums[slow] {
                    slow += 1;
                }
                while fast < len && curr_fast == nums[fast] {
                    fast += 1;
                }
            }
            Ordering::Less => {
                // 两个元素间的差值太小了, 移动 fast 指针
                fast += 1;
            }
            Ordering::Greater => {
                // 两个元素间的差值太大了, 移动 slow 指针
                slow += 1;
            }
        }
    }

    count
}
}

相关问题