LeetCode题目:Two Sum

By | 2012 年 11 月 1 日

很直接的算法,时间O(n2)。
如果要改进的话,可以先排序,内层二分来做。不过需要排序的时候记录下下标的变化,因为结果是要返回下标的。
而且,返回结果中的下标是从1开始的。



Two Sum
Given an array of integers, 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.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

代码:16ms过大集合

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> ret;
        if(numbers.size() <= 1) return ret;
        //find min/max for trim
        int vmin = numbers[0];
        int vmax = numbers[0];
        for(int i = 1; i < numbers.size(); ++i) {
            if(numbers[i] < vmin)
                vmin = numbers[i];
            if(numbers[i] > vmax)
                vmax = numbers[i];
        }
        for(int i0 = 0; i0 < numbers.size() - 1; ++ i0) {
            int v0 = numbers[i0];
            int starget = target - v0;
            if(starget < vmin || starget > vmax) continue;
            for(int i1 = i0 + 1; i1 < numbers.size(); ++ i1) {
                if(numbers[i1] == starget) {
                    ret.push_back(i0 + 1);
                    ret.push_back(i1 + 1);
                    return ret;
                }
            }
        }
        return ret;
    }
};

New C++ solution

// new C++ solution using map updated 2016-04-22
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> valueIndexMap;
        for(int i = 0; i < nums.size(); i++)
            valueIndexMap[nums[i]] = i;
        vector<int> indices;
        for(int i = 0; i < nums.size(); i++) {
            int remain = target - nums[i];
            if(valueIndexMap.find(remain) != valueIndexMap.end() && valueIndexMap[remain] != i){
                indices.push_back(i);
                indices.push_back(valueIndexMap[remain]);
                return indices;
            }
        }
        return indices;
    }
};

new Ruby solution

# ruby solution updated 2016-04-22
def two_sum(nums, target)
    map = {}
    nums.each_with_index{|v,i| map[v] = i}
    nums.each_with_index do |v,i|
        remain = target - v
        if (ri = map[remain]) != nil && i != ri
            return [i, ri]
        end
    end
end

new Java solution

// Java solution update 2016-04-22
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0 ; i < nums.length; i++){
            map.put(nums[i], i);
        }
        int[] result = new int[2];
        for(int i = 0 ; i < nums.length; i++){
            int remain = target - nums[i];
            if(map.containsKey(remain)){
               int ri = map.get(remain);
               if(i != ri){
                    result[0] = i;
                    result[1] = ri;
                    break;
                } 
            }

        }
        return result;
    }
}

new C solution updated 2016-04-22

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int * results = malloc(sizeof(int) * 2);
    bool found = false;
    for(int i = 0 ; i < numsSize && !found; ++i)
        for(int j = i+1 ; j < numsSize && !found; ++j){
            if(nums[i]+nums[j] == target){
                results[0] = i;
                results[1] = j;
                found = true;
            }
        }
    return results;
}

7 thoughts on “LeetCode题目:Two Sum

        1. uniEagle Post author

          哦,对哦,那就是hashmap好了。O(n)空间O(n)时间;如果排序方法的话,那是O(n)空间O(nlogn)时间不划算了。

          Reply

发表评论

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