图片 1Screenshot
from 2016-03-01 21:28:37.png

Given an array of integers that is already sorted in ascending order,
find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that
they add up to the target, where index1 must be less than index2. Please
note that your returned answers (both index1 and index2) are not
zero-based.
You may assume that each input would have exactly one solution and you
may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

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

1.描述

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

The function twoSum should return indices of the two numbers such that
they add up to the target, where index1 must be less than index2. Please
note that your returned answers (both index1 and index2) are not
zero-based.

You may assume that each input would have exactly one solution and you
may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

My code:

思路:双指针分别指向首尾,看和与target的大小关系,选择左移或右移指针。

The function twoSum should return indices of the two numbers such that
they add up to the target, where index1 must be less than index2. Please
note that your returned answers (both index1 and index2) are not
zero-based.

2.分析

public class Solution { public int[] twoSum(int[] numbers, int target) { if (numbers == null || numbers.length < 2) return null; HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>(); for (int i = 0; i < numbers.length; i++) { if (tracker.containsKey(numbers[i])) { int[] ret = new int[2]; ret[0] = tracker.get(numbers[i]) + 1; ret[1] = i + 1; return ret; } else { tracker.put(target - numbers[i], i); } } return null; }}
public int[] twoSum(int[] numbers, int target) {
    int[] res = new int[2];
    if (numbers == null || numbers.length < 2) {
        return new int[0];
    }

    int left = 0, right = numbers.length - 1;
    while (left < right) {
        if (numbers[left] + numbers[right] == target) {
            res[0] = left + 1;
            res[1] = right + 1;
            return res;
        } else if (numbers[left] + numbers[right] > target) {
            right--;
        } else {
            left++;
        }
    }

    return res;
}

You may assume that each input would have exactly one solution and you
may not use the same element twice.

3.代码

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    if (NULL == numbers || numbersSize < 2) return NULL;
    unsigned int index1 = 0;
    unsigned int index2 = numbersSize - 1;
    while (index1 < index2) {
        while (index1 < index2 && numbers[index1] + numbers[index2] < target) ++index1;
        while (index1 < index2 && numbers[index1] + numbers[index2] > target) --index2;
        if (numbers[index1] + numbers[index2] == target) {
            *returnSize = 2;
            int* returnNums = (int*)malloc((*returnSize)*sizeof(int));
            returnNums[0] = index1 + 1;
            returnNums[1] = index2 + 1;
            return returnNums;
        } 
    }
    return NULL;
}

不知道这道题目有什么意义。跟2sum不是差不多嘛?

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Anyway, Good luck, Richardo!

分析

一个已排序数组,寻找两个数字的和为指定值。很简单的二分查找即可实现,代码如下。

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int index1=0,index2=numbersSize-1;
    while(index1<index2)
    {
        if(numbers[index1]+numbers[index2]==target)
            break;
        else if(numbers[index1]+numbers[index2]<target)
        {
            index1++;
        }
        else
            index2--;
    }
    int *ans=(int*)malloc(sizeof(int)*2);
    ans[0]=index1+1;
    ans[1]=index2+1;
    *returnSize=2;
    return ans;
}

My code:

public class Solution { public int[] twoSum(int[] numbers, int target) { if (numbers == null || numbers.length == 0) { return null; } int begin = 0; int end = numbers.length - 1; while (begin < end) { int sum = numbers[begin] + numbers[end]; if (sum > target) { end--; } else if (sum < target) { begin++; } else { int[] ret = new int[2]; ret[0] = begin + 1; ret[1] = end + 1; return ret; } } return null; }}

reference:

看到这道题目,我首先想到了两个解法。第一个就是用hashtabletime: Ospace: O

第二种是用 遍历 + binary searchtime: Ospace: O

有没有种算法,time: Ospace: O

当然是有的。这种排好序的数列,就是天生为了双指针而存在的。

Anyway, Good luck, Richardo! — 09/02/2016

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图