每周一算法2017.11.17

TWO SUM

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

中文: 给定一个整型数组,找出能相加起来等于一个特定目标数字的两个数。

你可以假定每个输入都有且仅有一个解决方案,数字只能使用一次,给出他们的下标。

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

分析:这道题的思路是采用两层for循环,一层for循环取出数组中的元素,第二层for循环取出除去第一层for循环的元素,然后两者相加与目标数相比,如果相等就结束循环,否则就继续。

Time complexity : O(n^2)​
Space complexity : O(1)

代码:

java:

public int[] twoSum(int[] nums, int target) {  
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
}

swift:

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {

        for i in 0..<nums.count {
            for j  in i + 1 ..< nums.count {
                if nums[i] == target - j {
                    return [i, j]
                }
            }
        }
        return [1, 2]
 }

c++

class Solution {  
public:  
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> mapping;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++)
        {
            mapping[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            int searched = target - nums[i];
            if (mapping.find(searched) != mapping.end()
                && mapping.at(searched) != i)
            {
                result.push_back(i );
                result.push_back(mapping[searched]);
                break;
            }
        }
        return result;     
    }
};

本题来自leetcode

comments powered by Disqus