Buttercola: Zenefits: Two Minus
Zenefits: Two Minus
在一个整数数组中（有重复元素）找出有多少对，满足条件：他们的差等于k。例如[1,5,5,2,4,6,7]，k=3，满足条件的对子有[1,4], [2,5], [2,5]（注意有两个5）,[4,7]，所以程序返回4。这题比较tricky的地方在于k=0的情况需要另外考虑一下。
Solution:
1. Sort the array
2. Maintain two pointers, lo and hi, points to index 0 and 1, respectively.
3. If nums[hi] - nums[lo] == k. Add into result. Then we need to check the duplicates for lo + 1, lo + 2. .... If no duplicates, hi++.
4. if nums[hi] - nums[lo] > k. lo++
5. If nums[hi] - nums[lo] < k, hi++.
Solution:
1. Sort the array
2. Maintain two pointers, lo and hi, points to index 0 and 1, respectively.
3. If nums[hi] - nums[lo] == k. Add into result. Then we need to check the duplicates for lo + 1, lo + 2. .... If no duplicates, hi++.
4. if nums[hi] - nums[lo] > k. lo++
5. If nums[hi] - nums[lo] < k, hi++.
Read full article from Buttercola: Zenefits: Two Minus
No comments:
Post a Comment