↓ Skip to main content
111qqz’s blog
  1. Posts/

leetcode 532. K-diff Pairs in an Array （找差为k的数对）

·557 words·2 mins
ACM Leetcode
Note: This article is available in Chinese only. 本文暂无英文版本。 View original

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.

Example 1:

1Input: [3, 1, 4, 1, 5], k = 2
2Output: 2
3Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
4Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

1Input:[1, 2, 3, 4, 5], k = 1
2Output: 4
3Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

1Input: [1, 3, 1, 5, 4], k = 0
2Output: 1
3Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

  1. The pairs (i, j) and (j, i) count as the same pair.
  2. The length of the array won't exceed 10,000.
  3. All the integers in the given input belong to the range: [-1e7, 1e7].

思路：由于重复的只算一次，所以存两个set，分别为nums[i]和nums[i]+k.复杂度O(nlgn)

对于k=0的情况特殊处理，因为可能自己和自己组成一对…所以k=0可以排序然后找出现次数大于一次的元素，也是O(nlgn)

总体复杂度O(nlgn)

另外需要注意的是，两个数的绝对值可能是负数…..k<0返回0。。。

脑回路真是不一样。。。都绝对值了。。还负数。。。？出题人觉得没考虑到负数是考虑不周到？

然而我只觉得出题人傻逼。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年04月05日 星期三 14时25分00秒
 4File Name :532.cpp
 5 ************************************************ */
 6class Solution {
 7    public:
 8    int findPairs(vector<int>& nums, int k) {
 9        int siz = nums.size();
10        int res = 0 ;
11        if (k<0) return 0;
12        if (k==0)
13        {
14        sort(nums.begin(),nums.end());
15        nums.push_back(1E8);
16        for ( int i = 1 ; i < siz ; i++)
17        {
18            if (nums[i]==nums[i-1]&&nums[i]!=nums[i+1]) res++;
19        }
20        return res;
21        }
22        set<int>a;
23        set<int>b;
24        for ( int i = 0 ; i < siz;  i++)
25        {
26        a.insert(nums[i]+k);
27        b.insert(nums[i]);
28        }
29        for ( auto &it:a)
30        {
31        if (b.count(it)) res++;
32        }
33        return res;
34    }
35};

Related

leetcode 448. Find All Numbers Disappeared in an Array(寻找所有消失的元素）

·341 words·1 min
ACM Leetcode
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [5,6] 思路：由于元素大小有限制，是在1..n之间。

leetcode 105 根据前序遍历和中序遍历重构二叉树

·433 words·1 min
ACM Leetcode
思路： 分治搞之。 实际上两个vector就够了。。。4个会MLE(在leetcode上。。。 代码实现 1/** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { 11public: 12 TreeNode* res; 13 TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { 14 int siz = pre.size(); 15 if (siz==0) return NULL; 16 int rt = pre[0]; 17 int pos=-1; 18 for ( int i = 0 ; i < siz; i++) 19 if (vin[i]==rt) 20 { 21 pos = i; 22 break; 23 } 24 vector<int>preL,preR,vinL,vinR; 25 for ( int i = 0 ; i < pos ; i++) 26 { 27 preL.push_back(pre[i+1]); 28 vinL.push_back(vin[i]); 29 } 30 for ( int i = pos + 1 ; i < siz ; i++) 31 { 32 preR.push_back(pre[i]); 33 vinR.push_back(vin[i]); 34 } 35 TreeNode *head = new TreeNode(rt); 36 head->left = reConstructBinaryTree(preL,vinL); 37 head->right = reConstructBinaryTree(preR,vinR); 38 return head; 39 40 41 } 42}; 43 44 45 46 47/* *********************************************** 48Author :111qqz 49Created Time :2017年04月05日 星期三 16时21分35秒 50File Name :105.cpp 51************************************************ */ 52/** 53 54 * Definition for a binary tree node. 55 56 * struct TreeNode { 57 58 * int val; 59 60 * TreeNode *left; 61 62 * TreeNode *right; 63 64 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 65 66 * }; 67 68 */ 69 70class Solution { 71 72public: 73 74 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 75 76 int siz = preorder.size(); 77 if (siz==0) return NULL; 78 int rt = preorder[0]; 79 int pos; 80 for ( int i = 0 ; i < siz ; i++) 81 { 82 if (inorder[i]==rt) 83 { 84 pos = i; 85 break; 86 } 87 } 88 vector<int>preL,inL; 89 TreeNode *head = new TreeNode(rt); 90 for ( int i = 0 ; i < pos ; i++) 91 { 92 preL.push_back(preorder[i+1]); 93 inL.push_back(inorder[i]); 94 } 95 head->left = buildTree(preL,inL); 96 97 preL.clear(); 98 inL.clear(); 99 for ( int i = pos + 1 ; i < siz; i++) 100 { 101 preL.push_back(preorder[i]); 102 inL.push_back(inorder[i]); 103 } 104 head->right = buildTree(preL,inL); 105 return head; 106 107 } 108 109};

leetcode 74. Search a 2D Matrix

·183 words·1 min
ACM 二分 Leetcode
题目链接 题意：给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。 思路：单调。。显然二分。。。唯一的技巧是从右上角开始搜。 1/* *********************************************** 2Author :111qqz 3Created Time :2017年03月09日 星期四 19时03分07秒 4File Name :74.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 bool searchMatrix(vector<vector<int>>& matrix, int target) { 11 12 int n = matrix.size(); 13 if (n==0) return false; 14 int m = matrix[0].size(); 15 if (m==0) return false; 16 int row = 0 ; 17 int col = m-1; 18 while (col>=0&&row<n) 19 { 20 if (matrix[row][col]==target) return true; 21 else 22 if (matrix[row][col]>target) col--; 23 else row++; 24 } 25 return false; 26 27 } 28 29};

leetcode 437. Path Sum III

·242 words·1 min
ACM Brute Force Leetcode
题目链接 题意：求一棵二叉树中，所有一段连续路径之和等于给定值的路径数目。 思路：想了半天就只能想到暴力。。。复杂度大概O(n^2)。。。也不是不可以接受。。。但是感觉这也太暴力了。。就去看了题解。。。发现题解就还真是暴力orz。。。

leetcode 101. Symmetric Tree Add to List（二叉树，判断镜像）

·247 words·1 min
ACM Leetcode
题目链接 题意：判断一棵二叉树是否是自己的镜像。做法是做个copy，相当于两棵树做比较。注意逻辑不要漏掉就好 1/** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { 11public: 12 13 bool leaf(TreeNode* root) 14 { 15 if (root->left==NULL&&root->right==NULL) return true; 16 return false; 17 } 18 bool mirror(TreeNode* rt1,TreeNode* rt2) 19 { 20 21 if (rt1==NULL&&rt2==NULL) return true; 22 if (rt1==NULL||rt2==NULL) return false; 23 printf("%d %d\n",rt1->val,rt2->val); 24 if (leaf(rt1)&&leaf(rt2)&&rt1->val==rt2->val) return true; 25 if (leaf(rt1)||leaf(rt2)) return false; //包含了其中一个是叶子，或者两个都是叶子但是值不相等的情况。 26 if (rt1->val!=rt2->val) return false; //不是叶子，但是值不相等，没必要继续了。 27 bool res = true; 28 res = mirror(rt1->left,rt2->right); 29 if (!res) return false; 30 res = mirror(rt2->left,rt1->right); 31 if (!res) return false; 32 return true; 33 } 34 bool isSymmetric(TreeNode* root) { 35 if (root==NULL) return true; 36 return mirror(root,root); 37 38 } 39};