美文网首页
(leetcode)two sum

(leetcode)two sum

作者: 李云轩 | 来源:发表于2016-05-17 17:23 被阅读0次

problem

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.

example

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

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

因为一些蛋疼的原因我的个人页是用英文写的,因为刚开始写leetcode,还在用ide做测试,就把测试部分的代码也加了上来……

my first try

C++(with the test module):

#include "stdafx.h"
#include <iostream>
#include <vector>

using namespace std;

class Solution 
{
public:
    vector<int> static twoSum(vector<int>& nums, int target) 
    {
        vector<int> id;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    id.push_back(i);
                    id.push_back(j);
                    return id;
                }
            }
        }
        return id;
    }
};


int main(void)
{
    int n , target = 0;
    cin >> n;
    vector<int> nums(n);
    vector<int> id;
    for (int i = 0; i < nums.size(); i++) {
        cin >> nums[i];
    }
    cout << "Input your target:" << endl;
    cin >> target;
    id = Solution::twoSum(nums, target);
    for (vector<int>::iterator it = id.begin(); it < id.end(); it++) {
        cout << *it<<" ";
    }
    system("pause");
    return 0;
}                            

another solution using hash table:

C++:

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution 
{
public:
    vector<int> static twoSum(vector<int>& nums, int target) 
    {
        vector<int> id;
        unordered_map<int, int> hash;  //数组的值为key,索引i为hash表的值
        for (int i = 0; i < nums.size(); i++) {
            if (hash.find(target - nums[i]) != hash.end()) {  //在hash表中找不到对应的数,就将之存入hash表
                id.push_back(hash[target - nums[i]]);        
                id.push_back(i);
                return id;
            }
            hash[nums[i]] = i;
        }
        return id;
    }
};


int main(void)
{
    int n , target = 0;
    cin >> n;
    vector<int> nums(n);
    vector<int> id;
    for (int i = 0; i < nums.size(); i++) {
        cin >> nums[i];
    }
    cout << "Input your target:" << endl;
    cin >> target;
    id = Solution::twoSum(nums, target);
    for (vector<int>::iterator it = id.begin(); it < id.end(); it++) {
        cout << *it<<" ";
    }
    system("pause");
    return 0;
}

{% endcodeblock %}

Java version:
{% codeblock [lang:Java] %}

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;


public class Solution {
    
    public static int[] twoSum(int[] nums,int target){
        int[] id = new int[2];
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target) {
                    id[0] = i;
                    id[1] = j;
                    return id;
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0;i<nums.length;i++){
            nums[i] = sc.nextInt();
        }
        System.out.println("Input your target:");
        int target  = sc.nextInt();
        int[] id = new int[2];
        id = Solution.twoSum(nums, target);
        System.out.print(id[0]);
        System.out.print(' ');
        System.out.print(id[1]);
    }
}

using hash table:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.HashMap;

public class Solution {
    
    public static int[] twoSum(int[] nums,int target){
        int[] id = new int[2];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i< nums.length;i++){
            if(map.get(target-nums[i])!=null) {
                int[] result = {map.get(nums[i])+1,i+1};
                return result;
            }
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0;i<nums.length;i++){
            nums[i] = sc.nextInt();
        }
        System.out.println("Input your target:");
        int target  = sc.nextInt();
        int[] id = new int[2];
        id = Solution.twoSum(nums, target);
        System.out.print(id[0]);
        System.out.print(' ');
        System.out.print(id[1]);
    }
}

原文地址:我的主页文章

相关文章

网友评论

      本文标题:(leetcode)two sum

      本文链接:https://www.haomeiwen.com/subject/rnpirttx.html