q****m
发帖数: 177 | 1 这道题目需要返回index, time complexity
能到多少啊? | c*****a
发帖数: 808 | | q****m
发帖数: 177 | 3 不知道shuz数值范围的话没办法用hash
【在 c*****a 的大作中提到】
: 好像是用hash的o(n)?
: 求牛人的最优解法
| q****m
发帖数: 177 | 4 可以先search,找到最大max和最小min
然后用size为max -min+1的 bool array 来hash.
【在 c*****a 的大作中提到】
: 好像是用hash的o(n)?
: 求牛人的最优解法
| c********t
发帖数: 5706 | 5 不是整数吗？你是怕hash table太大？
把题目link发一下吧。
【在 q****m 的大作中提到】
: 不知道shuz数值范围的话没办法用hash
| c*****a
发帖数: 808 | 6 你的意思是不是, 找max和min是数值范围然后建一个bool[max-min+1]的hash ?
我是用collection的hash做的
public class Solution {
public int[] twoSum(int[] numbers, int target) {
// Start typing your Java solution below
// DO NOT write main() function
int []result = new int[2];
Map set = new HashMap();// key
-value, index
for(int i =0; i
if(set.containsKey(target - numbers[i])){
result[0] = set.get(target -numbers[i]);
result[1] = i+1;
return result;
}
else set.put(numbers[i], i+1);
}
return result;
}
} | Q*******e
发帖数: 939 | 7 how about number like:
0, 1, 2, 3, 4, 5, 2^32-1,2^32-2, 2^32-3
【在 q****m 的大作中提到】
: 可以先search,找到最大max和最小min
: 然后用size为max -min+1的 bool array 来hash.
| q****m
发帖数: 177 | 8 对于这样的情况，即使用brute force也是需要考虑，在A[i]+A[j]==target 的判断里，
A[i]+A[j]可能会溢出
【在 Q*******e 的大作中提到】
: how about number like:
: 0, 1, 2, 3, 4, 5, 2^32-1,2^32-2, 2^32-3
| Q*******e
发帖数: 939 | 9 use INT32_MAX - A[i] < A[j]
to avoid overflow before adding
里，
【在 q****m 的大作中提到】
: 对于这样的情况，即使用brute force也是需要考虑，在A[i]+A[j]==target 的判断里，
: A[i]+A[j]可能会溢出
| q****m
发帖数: 177 | 10 是可以有办法防止，如果是负数的话需要用INT32_MIN
【在 Q*******e 的大作中提到】
: use INT32_MAX - A[i] < A[j]
: to avoid overflow before adding
:
: 里，
| Q*******e
发帖数: 939 | 11 这个CMU的secure/professional c/c++ programming有讲
【在 q****m 的大作中提到】
: 是可以有办法防止，如果是负数的话需要用INT32_MIN
|
|
