[LeetCode From Day One] - Two Pointers K-diff in an Array

发表于 2019年05月06日 · 归类于 Algorithm · 阅读量加载中...

本文是双指针系列的第三篇了，本题要比之前的Two Pointers I和Two Pointers III涉及的题目要难一点。本题是Amazon的笔试/面试题，要求在给定的数组中找到差的绝对值等于K的所有pair。

给定一个整数数组和一个整数k，要求找到所有的(i,j)对，它们的差的绝对值恰好为k。输出这样的pair的数量，注意要去重。 Example：
Input: [3,1,4,1,5]
Output: 2 Expaination: 共有两个对的差的绝对值为k，(1,3)和(3,5)。虽然有两个1，但是题目要求unique。

首先能想到的方法是，对数组的元素做一个索引，然后遍历每个元素x，去索引中查找x+k的元素存在与否。这也是本题Discussion中vote数最多的解法，使用HashMap，对数组与map的key分别做一次遍历，时间复杂度为$O(n)$，有兴趣的可以去看看代码。这种方式在第一趟遍历简历索引时就已经对元素去重了。

这里给出一种使用双指针的解法。基本的算法思想：两个指针遍历一个排好序的数组，快指针去找比慢指针大k的元素，慢指针遍历数组，跳过重复元素。代码如下：

class Solution {
    public int findPairs(int[] nums, int k) {
        int cnt = 0;
        Arrays.sort(nums);
        for(int i = 0, j = 0; i < nums.length; ++i) {
            for(j = Math.max(j, i+1); j < nums.length && nums[j] - nums[i] < k; ++j) ;
            if(j < nums.length && nums[j] - nums[i] == k) ++cnt;
            while(i < nums.length - 1 && nums[i+1] == nums[i]) ++i;
        }
        return cnt;
    }
}

算法首先对数组进行排序。第一个for循环表示慢指针，遍历数组元素。嵌套的for循环中，快指针找到第一个元素，使得nums[j]-nums[i] >= k。if语句判断插值是否为k。嵌套的while循环跳过所有的重复值。

算法的时间复杂度为$O(n\log{n})$，空间复杂度为$O(1)$。

[LeetCode From Day One] - Two Pointers K-diff in an Array

相关文章