2014
01-10

面试题精选100题(10)－排序数组中和为给定值的两个数字[算法]

///////////////////////////////////////////////////////////////////////
// Find two numbers with a sum in a sorted array
// Output: ture is found such two numbers, otherwise false
///////////////////////////////////////////////////////////////////////
bool FindTwoNumbersWithSum
(
int data[],           // a sorted array
unsigned int length,  // the length of the sorted array
int sum,              // the sum
int& num1,            // the first number, output
int& num2             // the second number, output
)
{

bool found = false;
if(length < 1)
return found;

int ahead = length - 1;
int behind = 0;

{
long long curSum = data[ahead] + data[behind];

// if the sum of two numbers is equal to the input
// we have found them
if(curSum == sum)
{
num1 = data[behind];
found = true;
break;
}
// if the sum of two numbers is greater than the input
// decrease the greater number
else if(curSum > sum)
// if the sum of two numbers is less than the input
// increase the less number
else
behind ++;
}

return found;
}

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

2. [email protected]

3. for(int i=1; i<=m; i++){
for(int j=1; j<=n; j++){
dp = dp [j-1] + 1;
if(s1.charAt(i-1) == s3.charAt(i+j-1))
dp = dp[i-1] + 1;
if(s2.charAt(j-1) == s3.charAt(i+j-1))
dp = Math.max(dp [j - 1] + 1, dp );
}
}
这里的代码似乎有点问题？ dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false