排序数组中找2个数，使其差等于一个给定值# JobHunting - 待字闺中
m*0
1 楼
如题，数组中都是正数且为unique number，找出两个数A、B，so that A-B = 一个给
定的数C。要求使用常数空间（so hash map不能用）、O(N)时间。请问这个题有什么思
路吗？
定的数C。要求使用常数空间（so hash map不能用）、O(N)时间。请问这个题有什么思
路吗？
h*c
2 楼
is it sorted?
if sorted,
possibly big number - small number > C
narrow down.
if sorted,
possibly big number - small number > C
narrow down.
S*s
3 楼
[a1,a2,a3,a4,a5,a6,a7], 有几种可能, assume you have two indexes point: i = 0
, j = array.length - 1
if a7 - a1 < C, return null
if a7 - a1 > C, you can either move i to right side or move j to left side.
不确定这个一定能找到
如果是和等于一个定数，那倒是可以用上面的方法找到。
, j = array.length - 1
if a7 - a1 < C, return null
if a7 - a1 > C, you can either move i to right side or move j to left side.
不确定这个一定能找到
如果是和等于一个定数，那倒是可以用上面的方法找到。
W*y
4 楼
两个指针都从0开始
vector findGapC(vector &A)
{
int p1 = 0, p2 = 1, len = A.size();
vector ret;
if(len<2) return ret;
while(p1
ret.push_back(A[p1]);
ret.push_back(A[p2]);
return ret;
}
else if(A[p2] - A[p1]
if(p2==p1) p2 = p1+1;
}
return ret;
}
0
.
【在 S********s 的大作中提到】
: [a1,a2,a3,a4,a5,a6,a7], 有几种可能, assume you have two indexes point: i = 0
: , j = array.length - 1
: if a7 - a1 < C, return null
: if a7 - a1 > C, you can either move i to right side or move j to left side.
: 不确定这个一定能找到
: 如果是和等于一个定数，那倒是可以用上面的方法找到。
vector
{
int p1 = 0, p2 = 1, len = A.size();
vector
if(len<2) return ret;
while(p1
ret.push_back(A[p1]);
ret.push_back(A[p2]);
return ret;
}
else if(A[p2] - A[p1]
if(p2==p1) p2 = p1+1;
}
return ret;
}
0
.
【在 S********s 的大作中提到】
: [a1,a2,a3,a4,a5,a6,a7], 有几种可能, assume you have two indexes point: i = 0
: , j = array.length - 1
: if a7 - a1 < C, return null
: if a7 - a1 > C, you can either move i to right side or move j to left side.
: 不确定这个一定能找到
: 如果是和等于一个定数，那倒是可以用上面的方法找到。
s*3
5 楼
我的想法是，把排序数组在左边镜像一下，镜像的那一般就都成负数了。
比方说原始数组是1， 3， 6， 9， 那变换之后成了 -9， -6， -3， -1， 1, 3， 6
， 9
这样就成了在排序数组中找两个数和为一个特定值。
就直接用两个指针前后开始走。
求拍。
比方说原始数组是1， 3， 6， 9， 那变换之后成了 -9， -6， -3， -1， 1, 3， 6
， 9
这样就成了在排序数组中找两个数和为一个特定值。
就直接用两个指针前后开始走。
求拍。
h*d
6 楼
可能得出错误解
而且用了o(n)空间
6
★ 发自iPhone App: ChineseWeb 7.8
【在 s*********3 的大作中提到】
: 我的想法是，把排序数组在左边镜像一下，镜像的那一般就都成负数了。
: 比方说原始数组是1， 3， 6， 9， 那变换之后成了 -9， -6， -3， -1， 1, 3， 6
: ， 9
: 这样就成了在排序数组中找两个数和为一个特定值。
: 就直接用两个指针前后开始走。
: 求拍。
而且用了o(n)空间
6
★ 发自iPhone App: ChineseWeb 7.8
【在 s*********3 的大作中提到】
: 我的想法是，把排序数组在左边镜像一下，镜像的那一般就都成负数了。
: 比方说原始数组是1， 3， 6， 9， 那变换之后成了 -9， -6， -3， -1， 1, 3， 6
: ， 9
: 这样就成了在排序数组中找两个数和为一个特定值。
: 就直接用两个指针前后开始走。
: 求拍。
b*q
7 楼
这样就不是constant space了
6
【在 s*********3 的大作中提到】
: 我的想法是，把排序数组在左边镜像一下，镜像的那一般就都成负数了。
: 比方说原始数组是1， 3， 6， 9， 那变换之后成了 -9， -6， -3， -1， 1, 3， 6
: ， 9
: 这样就成了在排序数组中找两个数和为一个特定值。
: 就直接用两个指针前后开始走。
: 求拍。
6
【在 s*********3 的大作中提到】
: 我的想法是，把排序数组在左边镜像一下，镜像的那一般就都成负数了。
: 比方说原始数组是1， 3， 6， 9， 那变换之后成了 -9， -6， -3， -1， 1, 3， 6
: ， 9
: 这样就成了在排序数组中找两个数和为一个特定值。
: 就直接用两个指针前后开始走。
: 求拍。
k*e
8 楼
先排序然后维护两个指针向后shift
【在 m******0 的大作中提到】
: 如题，数组中都是正数且为unique number，找出两个数A、B，so that A-B = 一个给
: 定的数C。要求使用常数空间（so hash map不能用）、O(N)时间。请问这个题有什么思
: 路吗？
【在 m******0 的大作中提到】
: 如题，数组中都是正数且为unique number，找出两个数A、B，so that A-B = 一个给
: 定的数C。要求使用常数空间（so hash map不能用）、O(N)时间。请问这个题有什么思
: 路吗？
T*e
9 楼
[a1, a2, a3, a4, a5, ... aN]
像做substring的题一样维护一个window，例如left和right，然后有个diffSum记录相
邻两个数差的和，left和right都从index=1开始，每一次循环都检查当前的差的和是不
是大于target，大于的话就从left开始减，减到right或者差和小于等于target为止：
int diffSum = 0;
for (int right = 1, left = 1; right < N; right++) {
diffSum += a[right] - a[right-1];
while (diffSum > target && left <= right) {
diffSum -= a[left] - a[left-1];
left++;
}
if (diffSum == target) return pair(left-1, right);
}
像做substring的题一样维护一个window，例如left和right，然后有个diffSum记录相
邻两个数差的和，left和right都从index=1开始，每一次循环都检查当前的差的和是不
是大于target，大于的话就从left开始减，减到right或者差和小于等于target为止：
int diffSum = 0;
for (int right = 1, left = 1; right < N; right++) {
diffSum += a[right] - a[right-1];
while (diffSum > target && left <= right) {
diffSum -= a[left] - a[left-1];
left++;
}
if (diffSum == target) return pair
}
w*a
10 楼
这个靠谱
【在 W*********y 的大作中提到】
: 两个指针都从0开始
: vector findGapC(vector &A)
: {
: int p1 = 0, p2 = 1, len = A.size();
: vector ret;
: if(len<2) return ret;
: while(p1
: ret.push_back(A[p1]);
: ret.push_back(A[p2]);
【在 W*********y 的大作中提到】
: 两个指针都从0开始
: vector
: {
: int p1 = 0, p2 = 1, len = A.size();
: vector
: if(len<2) return ret;
: while(p1
: ret.push_back(A[p1]);
: ret.push_back(A[p2]);
l*i
11 楼
Let the array A = [a1,a2,...,an], sorted so that a1 <= a2 <= ... <=an
and we are looking for a[i] and a[j] such that a[j] - a[i] = K where K is
given.
start with a[1], and look for the first index t1 such that a[t1] >= a[1] + K
. If a[t1] = a[1] + K, we are done. Otherwise we move to a[2], and check
whether a[2] + K >= a[t1] or not. if equal, we are done, else if less, then
we move to a[3], else greater, then we move t1 to t1 + 1.
Algorithm:
left = 1, right = 1
while (right <= n) { // invariant: a[left] + K > a[right-1]
if a[left] + K == a[right] then return solution(left, right)
else if a[left] + K < a[right] then left = left + 1
else right = right + 1
}
return "no solution"
and we are looking for a[i] and a[j] such that a[j] - a[i] = K where K is
given.
start with a[1], and look for the first index t1 such that a[t1] >= a[1] + K
. If a[t1] = a[1] + K, we are done. Otherwise we move to a[2], and check
whether a[2] + K >= a[t1] or not. if equal, we are done, else if less, then
we move to a[3], else greater, then we move t1 to t1 + 1.
Algorithm:
left = 1, right = 1
while (right <= n) { // invariant: a[left] + K > a[right-1]
if a[left] + K == a[right] then return solution(left, right)
else if a[left] + K < a[right] then left = left + 1
else right = right + 1
}
return "no solution"
l*o
12 楼
else if(A[p2] - A[p1]>C) p1++; has problem.
p1连续shift会miss opportunity.
【在 W*********y 的大作中提到】
: 两个指针都从0开始
: vector findGapC(vector &A)
: {
: int p1 = 0, p2 = 1, len = A.size();
: vector ret;
: if(len<2) return ret;
: while(p1
: ret.push_back(A[p1]);
: ret.push_back(A[p2]);
p1连续shift会miss opportunity.
【在 W*********y 的大作中提到】
: 两个指针都从0开始
: vector
: {
: int p1 = 0, p2 = 1, len = A.size();
: vector
: if(len<2) return ret;
: while(p1
: ret.push_back(A[p1]);
: ret.push_back(A[p2]);
i*e
13 楼
worst case 不是O(n) 而是 O(n^2)
【在 T******e 的大作中提到】
: [a1, a2, a3, a4, a5, ... aN]
: 像做substring的题一样维护一个window，例如left和right，然后有个diffSum记录相
: 邻两个数差的和，left和right都从index=1开始，每一次循环都检查当前的差的和是不
: 是大于target，大于的话就从left开始减，减到right或者差和小于等于target为止：
: int diffSum = 0;
: for (int right = 1, left = 1; right < N; right++) {
: diffSum += a[right] - a[right-1];
: while (diffSum > target && left <= right) {
: diffSum -= a[left] - a[left-1];
: left++;
【在 T******e 的大作中提到】
: [a1, a2, a3, a4, a5, ... aN]
: 像做substring的题一样维护一个window，例如left和right，然后有个diffSum记录相
: 邻两个数差的和，left和right都从index=1开始，每一次循环都检查当前的差的和是不
: 是大于target，大于的话就从left开始减，减到right或者差和小于等于target为止：
: int diffSum = 0;
: for (int right = 1, left = 1; right < N; right++) {
: diffSum += a[right] - a[right-1];
: while (diffSum > target && left <= right) {
: diffSum -= a[left] - a[left-1];
: left++;
x*9
14 楼
类似于two sum.
h*u
15 楼
a[n-1] - a[0] has the maximum difference
1: if a[n-1] - a[0] < C, stop, no solution.
2: if a[n-1] - a[0] == C, stop, find a solution.
3: if a[n-1] - a[0] > C, you can increase 0 to 1, or decrease n-1 to n-2.
Which one should be performed? It depends on a[n-1] - a[1] and a[n-2] - a[0].
if a[n-1] - a[1] > a[n-2] - a[0], increase 0 to 1.
else, decrease n-1 to n-2.
why? note that with this way, we will not loose to check any possible
difference value.
Complexity is O(n).
1: if a[n-1] - a[0] < C, stop, no solution.
2: if a[n-1] - a[0] == C, stop, find a solution.
3: if a[n-1] - a[0] > C, you can increase 0 to 1, or decrease n-1 to n-2.
Which one should be performed? It depends on a[n-1] - a[1] and a[n-2] - a[0].
if a[n-1] - a[1] > a[n-2] - a[0], increase 0 to 1.
else, decrease n-1 to n-2.
why? note that with this way, we will not loose to check any possible
difference value.
Complexity is O(n).
c*f
16 楼
please provide a case?
【在 l*********o 的大作中提到】
: else if(A[p2] - A[p1]>C) p1++; has problem.
: p1连续shift会miss opportunity.
【在 l*********o 的大作中提到】
: else if(A[p2] - A[p1]>C) p1++; has problem.
: p1连续shift会miss opportunity.
U*A
17 楼
假定排序由小到大。
vector findABC(vector &v, int c){
int size = (int)v.size();
vector result;
int start=0;
int diff=0;
for(int i=1; i
while (diff>c){
while(diff>c && startdiff = diff -(v[start+1]-v[start]);
start ++;
}
}
if(diff == c){
result.push_back(v[start]);
result.push_back(v[i]);
break;
}
}
return result;
}
vector
int size = (int)v.size();
vector
int start=0;
int diff=0;
for(int i=1; i
while (diff>c){
while(diff>c && startdiff = diff -(v[start+1]-v[start]);
start ++;
}
}
if(diff == c){
result.push_back(v[start]);
result.push_back(v[i]);
break;
}
}
return result;
}
e*5
18 楼
似乎行得通，不需要显示存镜像数组。 保存两个index i，j>=0, i对应的是B, j对应
的是A。i，j初始都是n-1, n-1。num[j]-num[i]=A-B. 如果num[j]-num[i]>target, j-
-; 如果num[j]-num[i]
【在 b**q 的大作中提到】
: 这样就不是constant space了
:
: 6
的是A。i，j初始都是n-1, n-1。num[j]-num[i]=A-B. 如果num[j]-num[i]>target, j-
-; 如果num[j]-num[i]
【在 b**q 的大作中提到】
: 这样就不是constant space了
:
: 6
e*5
19 楼
不错！赞一个。
0].
【在 h*****u 的大作中提到】
: a[n-1] - a[0] has the maximum difference
: 1: if a[n-1] - a[0] < C, stop, no solution.
: 2: if a[n-1] - a[0] == C, stop, find a solution.
: 3: if a[n-1] - a[0] > C, you can increase 0 to 1, or decrease n-1 to n-2.
: Which one should be performed? It depends on a[n-1] - a[1] and a[n-2] - a[0].
: if a[n-1] - a[1] > a[n-2] - a[0], increase 0 to 1.
: else, decrease n-1 to n-2.
: why? note that with this way, we will not loose to check any possible
: difference value.
: Complexity is O(n).
0].
【在 h*****u 的大作中提到】
: a[n-1] - a[0] has the maximum difference
: 1: if a[n-1] - a[0] < C, stop, no solution.
: 2: if a[n-1] - a[0] == C, stop, find a solution.
: 3: if a[n-1] - a[0] > C, you can increase 0 to 1, or decrease n-1 to n-2.
: Which one should be performed? It depends on a[n-1] - a[1] and a[n-2] - a[0].
: if a[n-1] - a[1] > a[n-2] - a[0], increase 0 to 1.
: else, decrease n-1 to n-2.
: why? note that with this way, we will not loose to check any possible
: difference value.
: Complexity is O(n).
T*e
20 楼
worst case为什么是O(n^2)呢，两个指针都只向前走而不会后退，相邻两个数的差最多
算两次，worst case O(2n)吧
【在 i*******e 的大作中提到】
: worst case 不是O(n) 而是 O(n^2)
算两次，worst case O(2n)吧
【在 i*******e 的大作中提到】
: worst case 不是O(n) 而是 O(n^2)
C*a
21 楼
和two sum没啥本质区别。
c*e
22 楼
这个方法可以么？
//假设数组排序了，而且都是unique的
bool func(int A[], int n， int k ){
unordered_set s;
//都insert 到set里面去
for(int i = 0; i < n; i++){
s.insert(A[i]);
}
for(int i = 0; i < n; i++){
if(s.find(A[i]+k)!=s.end()){
return true;
}
}
return false;
}
//假设数组排序了，而且都是unique的
bool func(int A[], int n， int k ){
unordered_set
//都insert 到set里面去
for(int i = 0; i < n; i++){
s.insert(A[i]);
}
for(int i = 0; i < n; i++){
if(s.find(A[i]+k)!=s.end()){
return true;
}
}
return false;
}
p*a
23 楼
常数空间，不让set
【在 c******e 的大作中提到】
: 这个方法可以么？
: //假设数组排序了，而且都是unique的
: bool func(int A[], int n， int k ){
: unordered_set s;
: //都insert 到set里面去
: for(int i = 0; i < n; i++){
: s.insert(A[i]);
: }
: for(int i = 0; i < n; i++){
: if(s.find(A[i]+k)!=s.end()){
【在 c******e 的大作中提到】
: 这个方法可以么？
: //假设数组排序了，而且都是unique的
: bool func(int A[], int n， int k ){
: unordered_set
: //都insert 到set里面去
: for(int i = 0; i < n; i++){
: s.insert(A[i]);
: }
: for(int i = 0; i < n; i++){
: if(s.find(A[i]+k)!=s.end()){
a*r
24 楼
0， 1 ，3 ，10 target 3.怎么办啊 似乎不行
0].
【在 h*****u 的大作中提到】
: a[n-1] - a[0] has the maximum difference
: 1: if a[n-1] - a[0] < C, stop, no solution.
: 2: if a[n-1] - a[0] == C, stop, find a solution.
: 3: if a[n-1] - a[0] > C, you can increase 0 to 1, or decrease n-1 to n-2.
: Which one should be performed? It depends on a[n-1] - a[1] and a[n-2] - a[0].
: if a[n-1] - a[1] > a[n-2] - a[0], increase 0 to 1.
: else, decrease n-1 to n-2.
: why? note that with this way, we will not loose to check any possible
: difference value.
: Complexity is O(n).
0].
【在 h*****u 的大作中提到】
: a[n-1] - a[0] has the maximum difference
: 1: if a[n-1] - a[0] < C, stop, no solution.
: 2: if a[n-1] - a[0] == C, stop, find a solution.
: 3: if a[n-1] - a[0] > C, you can increase 0 to 1, or decrease n-1 to n-2.
: Which one should be performed? It depends on a[n-1] - a[1] and a[n-2] - a[0].
: if a[n-1] - a[1] > a[n-2] - a[0], increase 0 to 1.
: else, decrease n-1 to n-2.
: why? note that with this way, we will not loose to check any possible
: difference value.
: Complexity is O(n).
p*a
25 楼
应该不会，后面有个 p1==p2 的情况
想不出什么例子.
【在 l*********o 的大作中提到】
: else if(A[p2] - A[p1]>C) p1++; has problem.
: p1连续shift会miss opportunity.
想不出什么例子.
【在 l*********o 的大作中提到】
: else if(A[p2] - A[p1]>C) p1++; has problem.
: p1连续shift会miss opportunity.
i*e
26 楼
想了一下， 两个指针不需要回头走，证明出来没问题。
你是对的 O(n)
【在 T******e 的大作中提到】
: worst case为什么是O(n^2)呢，两个指针都只向前走而不会后退，相邻两个数的差最多
: 算两次，worst case O(2n)吧
你是对的 O(n)
【在 T******e 的大作中提到】
: worst case为什么是O(n^2)呢，两个指针都只向前走而不会后退，相邻两个数的差最多
: 算两次，worst case O(2n)吧
d*n
27 楼
why do you need to check if p1 == p2? seems not neccessary.
]="" -="" a[p1]="=" c){="" :="" ret.push_back(a[p1]);="" :="" ret.push_back(
a[p2]);="" :="" ...................="">
【在 W*********y 的大作中提到】
: 两个指针都从0开始
: vector findGapC(vector &A)
: {
: int p1 = 0, p2 = 1, len = A.size();
: vector ret;
: if(len<2) return ret;
: while(p1
: ret.push_back(A[p1]);
: ret.push_back(A[p2]);
]="" -="" a[p1]="=" c){="" :="" ret.push_back(a[p1]);="" :="" ret.push_back(
a[p2]);="" :="" ...................="">
【在 W*********y 的大作中提到】
: 两个指针都从0开始
: vector
: {
: int p1 = 0, p2 = 1, len = A.size();
: vector
: if(len<2) return ret;
: while(p1
: ret.push_back(A[p1]);
: ret.push_back(A[p2]);
w*a
28 楼
相关阅读
一道M$面试题的解法...Liang Law: 申请H-1B后出入境美国相关问题孰重孰轻我的找工作经历 (统计类)一点感想(作为未来的IT 民工)法师请进 (转载关于面试)[合集] 关于cpt->opt->h1b的经验和教训USCIS CSC OPT Expedite Handling Request Info[合集] oracle问题GIS phone interview to share和大家分享我的找工作历程[合集] 我也来谈谈ICC:认清其本性在读CS PhD 找工经历（二）---柳暗花明，歪打正着坐在面试台的另一端rp小爆发，拿了个学校的offer[合集] 讲讲我家领导遇到的流氓律师[合集] 这HDD做决定也太快了吧参院讨论的Employment Based议案5个concern[ZT}关于negotiate 工资 (zt)我的on-site经验 ME Fresh PhD