j**y
发帖数: 462 | 1 detect if a sorted array contains two integer that sum up to 7. And then
improve your code so that the array is accessed with only one iteration
any solution for one iteration? |
g**e
发帖数: 6127 | 2 use hashset to store every item, for each a[i] check if set.Contains(7-a[i])
one pass, O(n) space
【在 j**y 的大作中提到】
: detect if a sorted array contains two integer that sum up to 7. And then
: improve your code so that the array is accessed with only one iteration
: any solution for one iteration?
|
i**********e
发帖数: 1145 | 3 Or a better way without using extra space is to use two pointers to traverse
the list. One from the start, the other from the end.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
j**y
发帖数: 462 | 4 that would be two iteration?
a[i])
【在 g**e 的大作中提到】
: use hashset to store every item, for each a[i] check if set.Contains(7-a[i])
: one pass, O(n) space
|
j**y
发帖数: 462 | 5 a bit unsure that would be one iteration as required.
traverse
【在 i**********e 的大作中提到】
: Or a better way without using extra space is to use two pointers to traverse
: the list. One from the start, the other from the end.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
c********1
发帖数: 52 | 6 array如果是sorted 保持两个指针 一个头一个尾往中间移动就行了
为什么不是one iteration as required？ |
g**e
发帖数: 6127 | 7 it's one iteration.
I didn't noticed it's a sorted array, so use head & tail pointers and scan
forward/backward. it's better.
【在 j**y 的大作中提到】
: that would be two iteration?
:
: a[i])
|
j**y
发帖数: 462 | 8 sorry 我以为是
for(from begin){
for(from end){
}
}
没想明白你怎么做，详细点？多谢
【在 c********1 的大作中提到】
: array如果是sorted 保持两个指针 一个头一个尾往中间移动就行了
: 为什么不是one iteration as required？
|
i**********e
发帖数: 1145 | 9 你先写出 7 的 two sum：
ie,
...
1+6
2+5
3+4
想想 怎么用排好序的特性来解决这题？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
g**f
发帖数: 414 | 10 刚写了一下，应该work。
O(1) space, O(n) time.
bool SumToS(int* array, const int len, const int S,
unsigned& ndx1, unsigned& ndx2)
{
int i = 0, j = len-1;
while (i != j) {
if (array[i] + array[j] < S) ++i;
else if (array[i] + array[j] > S) --j;
else {ndx1 = i; ndx2 = j; return true;}
}
return false;
} |
|
|
s*****y
发帖数: 897 | 11 The array should not be sorted.
Is it?
【在 g**f 的大作中提到】
: 刚写了一下，应该work。
: O(1) space, O(n) time.
: bool SumToS(int* array, const int len, const int S,
: unsigned& ndx1, unsigned& ndx2)
: {
: int i = 0, j = len-1;
: while (i != j) {
: if (array[i] + array[j] < S) ++i;
: else if (array[i] + array[j] > S) --j;
: else {ndx1 = i; ndx2 = j; return true;}
|
g**f
发帖数: 414 | 12 It is sorted.
【在 s*****y 的大作中提到】
: The array should not be sorted.
: Is it?
|
j**y
发帖数: 462 | 13 明白 多谢
【在 i**********e 的大作中提到】
: 你先写出 7 的 two sum：
: ie,
: ...
: 1+6
: 2+5
: 3+4
: 想想 怎么用排好序的特性来解决这题？
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
j**y
发帖数: 462 | 14 嗯 和我想的差不多 谢了
【在 g**f 的大作中提到】
: 刚写了一下，应该work。
: O(1) space, O(n) time.
: bool SumToS(int* array, const int len, const int S,
: unsigned& ndx1, unsigned& ndx2)
: {
: int i = 0, j = len-1;
: while (i != j) {
: if (array[i] + array[j] < S) ++i;
: else if (array[i] + array[j] > S) --j;
: else {ndx1 = i; ndx2 = j; return true;}
|
b*******8
发帖数: 37364 | 15 既然排序了，当然不用哈希了。能不用哈希就不用哈希，有些面试的不喜欢哈希，因为
哈希实际效果不一定好。BST是肯定有保证的。 |
