给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。
(注:返回的数组下标从1开始算起,保证target一定可以由数组里面2个数字相加得到)
数据范围:
,
,
要求:空间复杂度
,时间复杂度
[3,2,4],6
[2,3]
因为 2+4=6 ,而 2的下标为2 , 4的下标为3 ,又因为 下标2 < 下标3 ,所以返回[2,3]
[20,70,110,150],90
[1,2]
20+70=90
import java.util.*; public class Solution { /** * * @param numbers int整型一维数组 * @param target int整型 * @return int整型一维数组 */ public int[] twoSum (int[] numbers, int target) { // write code here Map<Integer, Integer> mem = new HashMap<>(); for (int i = 0; i < numbers.length; i++) { int another = target - numbers[i]; if (mem.containsKey(another) && mem.get(another) != i) { return new int[]{mem.get(another) + 1, i + 1}; } else mem.put(numbers[i], i); } return new int[]{}; } }
import java.util.HashMap; public class Solution { public int[] twoSum(int[] numbers, int target) { int n = numbers.length; int[] result = new int[2]; //map里面放 键为target-每个数的结果 值为下标 //每次放入的时候看是否包含 当前值 //有的话说明当前值和已包含的值下标的那个元素为需要的结果 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i=0;i<n;i++){ if(map.containsKey(numbers[i])){ result[0] = map.get(numbers[i])+1; result[1] = i+1; break; } else{ map.put(target - numbers[i], i); } } return result; } } 此题和leetcode上有所不同,leetcode上下标已改为从0开始
function twoSum( numbers , target ) { // write code here //定义一个hash表用来存放数据 var map=new Map() //获取数组的长度 var len=numbers.length //遍历数组 for(var i=0;i<len;i++) { //将目标数字减去数组中数字,得到差 var num=target-numbers[i] //如果哈希表中没有这个差,将这个数字放进去 if(!map.has(num)) { map.set(numbers[i],i+1) } else{ //如果有差,则获取到数字的下标 return [map.get(num),i+1] } } }
import java.util.HashMap;
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])){
return new int[]{map.get(nums[i])+1,i+1};
}
map.put(target - nums[i],i);
}
return null;
}
}
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
map<int, int> mapping;
vector<int> res;
for (int i = 0; i < numbers.size(); ++i) {
mapping[numbers[i]] = i;
}
for (int i = 0; i < numbers.size(); i++) {
int searched = target - numbers[i];
if (mapping.find(searched) != mapping.end() && i != mapping[searched]) {
res.push_back(i + 1);
res.push_back(mapping[searched] + 1);
break;
}
}
return res;
}
};
class Solution { public: /** * * @param numbers int整型vector * @param target int整型 * @return int整型vector */ vector<int> twoSum(vector<int>& numbers, int target) { unordered_map<int, int> m; for (int i = 0; i < numbers.size(); ++i) { if (m.find(target - numbers[i]) != m.end()) return {m[target - numbers[i]], i + 1}; m[numbers[i]] = i + 1; } return {-1, -1}; } };
class Solution: def twoSum(self , numbers: List[int], target: int) -> List[int]: # write code here tm= {} res = [] for i, v in enumerate(numbers): if v in tm: res.append(tm[v]+1) res.append(i+1) else: tm[target - v] = i return res
int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) { // write code here int *result = malloc(8); *returnSize = 2; for(int i = 0; i < numbersLen; i++) { // 过滤本身已经超过target的值,可以节省很多时间 if(numbers[i]>target) continue; for(int j = i+1;j < numbersLen; j++) if(numbers[i]+numbers[j] == target) { *result = i+1; *(result+1) = j+1; return result; } } return NULL; }没有过滤时间那一步,答案过不了。
/** * * @param numbers int整型一维数组 * @param target int整型 * @return int整型一维数组 */ function twoSum( numbers , target ) { const map = new Map() for(let i = 0;i < numbers.length;i++){ if(map.get(target - numbers[i]) !== undefined){ return [map.get(target - numbers[i])+1,i+1] } map.set(numbers[i],i) } } module.exports = { twoSum : twoSum };
package Array;
import java.util.Arrays;
import java.util.HashMap;
/**
* 1.Two Sum(两数之和)
* 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
* 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
*/
public class Solution1 {
public static void main(String[] args) {
Solution1 solution1 = new Solution1();
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = solution1.twoSum(nums, target);
System.out.println(Arrays.toString(result));
}
/**
* 用 HashMap 存储数组元素和索引的映射,在访问到 nums[i] 时,判断 HashMap 中是否存在 target - nums[i]
* 如果存在说明 target - nums[i] 所在的索引和 i 就是要找的两个数。
* 该方法的时间复杂度为 O(N),空间复杂度为 O(N),使用空间来换取时间。
*
* [@param nums
* @param target
* @return](/profile/547241) */
public int[] twoSum_2(int[] nums, int target) {
HashMap map = new HashMap();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]) + 1, i + 1};
} else {
map.put(nums[i], i);
}
}
return null;
}
/**
* 暴力,时间复杂度为 O(N^2)
*
* [@param nums
* @param target
* @return](/profile/547241) */
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[i] + nums[j] == target) {
return new int[]{i + 1, j + 1};
}
}
}
return null;
}
}
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param numbers int整型一维数组 * @param numbersLen int numbers数组长度 * @param target int整型 * @return int整型一维数组 * @return int* returnSize 返回数组行数 */ #include <math.h> #include <stdio.h> #include <stdlib.h> //使用拉链法解决冲突 typedef struct HashMapNode{ int data; struct HashMapNode* next; }HashMapNode,*HashMapHead; //这个函数用于给散列表添加元素 void addHashMapNode(HashMapHead* head,int index){ HashMapHead a = (HashMapHead)malloc(sizeof(HashMapNode)); a->data=index; a->next=NULL; if(*head==NULL){ *head=a; } else{ HashMapHead temp = *head; HashMapHead b; while(temp!=NULL){ b=temp; temp=temp->next; } a->next=b->next; b->next=a; } } int* twoSum(int* numbers, int numbersLen, int target, int* returnSize ) { // write code here int* result = (int*)malloc(2*sizeof(int)); *returnSize+=2; //创建一个散列表,大小:50000(主要是想尽量减少冲突的同时,又少用些内存) int hashMapLen = 50000; HashMapHead hash[hashMapLen]; //初始化散列表(这一步是挺浪费时间的,但是我真不知道怎么在c语言里初始化一个指针数组为null) for(int j=0;j<hashMapLen;j++){ hash[j]=NULL; } //work for(int i=0;i<numbersLen;i++){ //注意,求余在计算机语言中是可以出现负数的,因此要进行绝对值处理 int index=abs((numbers[i])%hashMapLen); //下面逻辑思路与官方思路相同 if(hash[index]!=NULL){ HashMapHead temp = hash[index]; while(temp!=NULL){ if(numbers[temp->data]+numbers[i]==target){ result[0] = temp->data+1; result[1] = i+1; return result; } temp=temp->next; } int newIndex=abs((target-numbers[i])%hashMapLen); addHashMapNode(&hash[newIndex],i); } else { int newIndex=abs((target-numbers[i])%hashMapLen); addHashMapNode(&hash[newIndex],i); } } return result; }此处给出该方法的效率,并与官方的散列表法作比较,以校验性能没问题。
import java.util.*; public class Solution { /** * * @param numbers int整型一维数组 * @param target int整型 * @return int整型一维数组 */ public int[] twoSum (int[] numbers, int target) { int len = numbers.length; int[] result = new int[2]; for(int i = 0; i < len; i++) { for(int j = i+1; j < len; j++) { if(numbers[i] + numbers[j] == target) { result[0] = i + 1; result[1] = j + 1; } } } return result; } }
public class Solution { /** * * @param numbers int整型一维数组 * @param target int整型 * @return int整型一维数组 */ public int[] twoSum (int[] numbers, int target) { // write code here Map<Integer,Integer> map = new HashMap<>(); for (int i = 0; i < numbers.length; i++) { if (map.containsKey(target - numbers[i])) { return new int[]{map.get(target - numbers[i])+1,i +1}; }else { map.put(numbers[i],i); } } return null; } }
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
map<int, int> m;
vector<int> res;
for(int i=0; i<numbers.size(); i++){
m[numbers[i]] = i;
}
for(int i=0; i<numbers.size(); i++){
const int diff = target - numbers[i];
if(m.find(diff) != m.end() && m[diff] > i){
res.push_back(i+1);
res.push_back(m[diff]+1);
break;
}
}
return res;
}
};
使用一个map保存每一个不同的数字最后出现的坐标,然后从下标0处开始进行查找。
即使有重复的数字,由于map中保存的是最后一次出现的位置,那样即使由两个相同
的值构成的数对也可以被找到。m[diff] > i,这个条件使用的比较好。
# 用例全部通过版本: class Solution: def twoSum(self , numbers: List[int], target: int) -> List[int]: # write code here for i in range(len(numbers) - 1): if numbers[i] <= target: # 用于降低时间复杂度 for j in range(i+1, len(numbers)): if numbers[i] + numbers[j] == target: return [i+1, j+1] return []
class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { unordered_map<int, int> hash; hash[numbers[0]]=1; for(int i=2;i<=numbers.size();++i){ if(hash.count(target-numbers[i-1])){ return {hash[target-numbers[i-1]], i}; } else { hash[numbers[i-1]]=i; } } return {}; } };