[Leetcode 167]Two Sum II — Input array is sorted

Description:

Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]

Constraints:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.

C code solution 1:

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
int * ans = (int*)malloc(sizeof(int)*2);
*returnSize = 2;
int i = 0, j = numbersSize-1;
while(i < j)
{
if(numbers[i] + numbers[j] == target)
{
ans[0] = i+1;
ans[1] = j+1;
return ans;
}
else if(numbers[i] + numbers[j] > target)
{
j--;
}
else
{
i++;
}
}
return NULL;
}

Explanation:

先取最前和最後的和看是否為target,若是則返回位置+1,若否且較target大,代表要減少些,所以將最右邊的index往左移一個。相反地,若較target小,將最左邊的index往右移一個,直到找到相加起來為target的兩數。此方法運用了這個array為non-decreasing的特性。時間複雜度為O(n)。

C code solution 2 (using hash):

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
*returnSize = 2; //return array must be 2
int* res = (int*)calloc(2, sizeof(int));
int hash[4001] = {0}; // idex: need, value: index in numbers + 1
for(int i=0; i<numbersSize; i++){
int need = target - numbers[i];
if(hash[need+1000] != 0){
res[0] = hash[need+1000]; // +1 already
res[1] = i + 1; // i has not yet +1
printf("%d %d", res[0], res[1]);
break;
}else{
hash[numbers[i]+1000] = i + 1;
}
}
return res;
}

Explanation:

運用hash查找的能力來加快。hash的index為array的某值,value為array某值的index。每次都看這個數還需要多少才會是target,設為 need 。若need有找到,代表前面有找過了,直接return兩個的位置+1。若沒找到,將此數的index作為值輸入hash中,而輸入的index為目前這個數的值。此方法亦為O(n),但前者在沒有排序下無法使用,而無論是否排序過,皆可透過hash可以達成。

Hi I am Samuel