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]);
}
}
