给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
数据范围：%20%5Cleq%2010%5E5)
，
，
要求：空间复杂度 )
，时间复杂度 )
[编程题]两数之和
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
HashMap<Integer, Integer> hash = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
int num=target-numbers[i];
if(hash.containsKey(num)){
int index=hash.get(num);
System.out.println(index+1);
System.out.println(i+1);
return new int[]{index+1,i+1};
}
hash.put(numbers[i],i);
}
return null;
}
}
发表于 2025-11-09 19:51:27
回复(0)
练练非hashmap的做法
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
int[] t = Arrays.copyOf(numbers, numbers.length);
Arrays.sort(t);
int left = 0;
int right = t.length - 1;
while (left <= right) {
if (t[left] + t[right] == target) {
break;
} else if (t[left] + t[right] > target) {
right--;
} else {
left++;
}
}
int[] res = new int[2];
int count = 0;
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == t[left] || numbers[i] == t[right]) {
res[count++] = i + 1;
if (count == 2) {
break;
}
}
}
return res;
}
}
发表于 2025-10-16 22:41:43
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
// 暴力求解
// for (int i = 0; i < numbers.length; i++) {
// for (int j = i + 1; j < numbers.length; j++) {
// if (numbers[i] + numbers[j] == target) {
// return new int[] {i + 1, j + 1};
// }
// }
// }
HashMap<Integer, Integer> map = new HashMap<>();
// 遍历数组
for (int i = 0; i < numbers.length; i++) {
// 计算目标数与当前数组的差
int complement = target - numbers[i];
// 判断map中是否包含该差值，有则获取该差值的value（索引）
if (map.containsKey(complement)) {
return new int[] {map.get(complement) + 1, i + 1};
}
// 没有则往map中添加元素
map.put(numbers[i], i);
}
return null;
}
}
发表于 2025-08-15 11:12:00
回复(0)
import java.util.*;
public class Solution {
// 二分查找
private int binarySearch(int[][] nums, int i, int j, int target) {
while (i <= j) {
int mid = (i + j) / 2;
if (nums[mid][0] == target) return mid;
if (nums[mid][0] > target) j = mid - 1;
else i = mid + 1;
}
return -1;
}
public int[] twoSum (int[] numbers, int target) {
//🍓 排序, 双指针 第二个数可二分查找 空间O(n) 时间O(nlogn)
int[][] nums = new int[numbers.length][2]; // numbers[i]及其下标+1
for (int i = 0; i < numbers.length; i++) {
nums[i][0] = numbers[i];
nums[i][1] = i + 1;
}
Arrays.sort(nums, (a, b)->a[0] - b[0]); // 排序
for (int i = 0; i < nums.length; i++) {
int j = binarySearch(nums, i + 1, nums.length - 1, target - nums[i][0]); // 二分查找
if (j > 0) {
int x = nums[i][1], y = nums[j][1];
return new int[] {Math.min(x,y), Math.max(x,y)};
}
}
//🍓 Map存, 空间O(n) 时间O(n) 因为题目保证一定有解
// Map<Integer, List<Integer>> map = new HashMap<>();
// for (int i = 0; i < numbers.length; i++) {
// List<Integer> list = map.getOrDefault(numbers[i], new ArrayList<Integer>());
// list.add(i + 1);
// map.put(numbers[i], list);
// }
// for (int i = 0; i < numbers.length; i++) {
// if (map.containsKey(target - numbers[i])) {
// List<Integer> list = map.get(target - numbers[i]);
// if (target == 2 * numbers[i] && list.size() == 1) continue; // 重但1个
// int k = 0;
// while (list.get(k) == i + 1) k++;
// int j = list.get(k);
// return new int[] {Math.min(i + 1, j), Math.max(i + 1, j)};
// }
// }
return null;
}
}
发表于 2025-03-27 15:01:23
回复(0)
public int[] twoSum (int[] numbers, int target) {
int[] result = new int[] {-1, -1};
int[] tmp = new int[numbers.length];
System.arraycopy(numbers, 0, tmp, 0, numbers.length);
//利用jdk工具类进行排序，时间复杂度nlogn
Arrays.sort(numbers);
int a = -11, b = -11;
// 时间复杂度nlogn
for (int i = 0; i < numbers.length; i++) {
a = numbers[i];
b = target - numbers[i];
// 每次二分查找和为target的另一个数字
if (binarySearch(numbers, i + 1, numbers.length - 1, b)) {
break;
}
}
// 查找满足和为target的2个数的下标
for (int i = 0; i < tmp.length; i++) {
if (tmp[i] == a && result[0] == -1) {
result[0] = i + 1;
} else if (tmp[i] == b && result[1] == -1) {
result[1] = i + 1;
}
}
// 返回的下标按升序排列
if (result[0] > result[1]) {
int tp = result[0];
result[0] = result[1];
result[1] = tp;
}
return result;
}
private boolean binarySearch(int[] numbers, int l, int r, int n) {
if (l <= r) {
int c = (l + r) / 2;
if (n < numbers[c]) {
return binarySearch(numbers, l, c - 1, n);
} else if (n > numbers[c]) {
return binarySearch(numbers, c + 1, r, n);
} else {
return true;
}
}
return false;
}
发表于 2023-09-29 21:07:00
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
if(numbers.length<=1){
// 如果传入的数组为空，或者只有一个数字
return null;
}
int[] result=new int[2];
for(int i=0;i<numbers.length;i++){
if(numbers[i]>target){//过滤本身已经超过target的值，可以节约时间
//建议使用hashMap，双循环超时，使用了这句代码只是在卡用例不全面，如果第一个是比target大的数字，第二个是个负数，两个加起来刚好等于target的话，就是有问题的
continue;
}
for(int j=i+1;j<numbers.length;j++){
if(numbers[i]+numbers[j]==target){
result[0]=i+1;
result[1]=j+1;
return result;
}
}
}
return null;
}
}
发表于 2023-08-19 11:25:02
回复(0)
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> map = new HashMap<Integer, Integer>();
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);
}
}
throw new IllegalArgumentException("no solution");
}
}
发表于 2023-08-14 11:29:18
回复(0)
int[] array = new int[]{2,4,7,8,21,14,17,18}; int target = 39; int[] result = new int[2]; boolean flag = false; for (int i=0; i<array.length; i++){ int temp = target - array[i]; if (flag) break; for(int j=0; j<array.length; j++){ if(i != j && temp == array[j]){ result[0] = i+1; result[1] = j+1; flag = true; break; } } } System.out.println(JSONObject.toJSON(result));
发表于 2023-07-28 17:31:35
回复(0)
public int[] twoSum (int[] numbers, int target) {
//因为返回的是下标
int[] ans=new int[2];
if(numbers==null||numbers.length==0) return ans;
for(int i=0;i<numbers.length;i++){
//截止条件
if(map.containsKey(target-numbers[i])){
//因为数组下标从1算起，所以这里的值都要+1
ans[0]=Math.min(i+1,map.get(target-numbers[i])+1);
ans[1]=Math.max(i+1,map.get(target-numbers[i])+1);
break;
}
map.put(numbers[i],i);
}
return ans;
}
发表于 2023-07-14 09:40:00
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
// 先对数组进行排序，利用二分法查找
int[] sort = numbers.clone();
Arrays.sort(sort);
// 中间索引
int medIndex = 0;
// 数组长度
int len = sort.length;
for (int i = 0; i < len; i++) {
int left = i + 1;
int right = len - 1;
while (left <= right) {
// 与中间元素比较
medIndex = (right + left) / 2;
if (sort[i] + sort[medIndex] == target) {
return find(numbers, sort[i], sort[medIndex]);
}
if (sort[i] + sort[medIndex] < target) {
left = medIndex + 1;
continue;
}
if (sort[i] + sort[medIndex] > target) {
right = medIndex - 1;
}
}
}
return null;
}
public int[] find(int[] arr, int a, int b) {
int[] result = new int[2];
int index1 = 0;
int index2 = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == a) {
index1 = i;
break;
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] == b && i != index1) {
index2 = i;
break;
}
}
if (index1 < index2) {
result[0] = index1 + 1;
result[1] = index2 + 1;
} else {
result[0] = index2 + 1;
result[1] = index1 + 1;
}
return result;
}
}
题目要求复杂度是O(nlogn)，那么显而易见就是一次循环加每个循环里一个二分查找。
发表于 2023-06-21 13:31:22
回复(0)
public int[] twoSum (int[] numbers, int target) {
//hashmap
int nums = numbers.length;
Map<Integer,Integer> map =new HashMap<>();
for (int i = 0; i < nums ; i++) {
if(map.containsKey(target - numbers[i])){
// map 包含 返回
// 第i个找到 所以后面是i+1 前面的通过map get value
return new int[]{(map.get(target - numbers[i]))+1, i+1};
}else{
//是把自己放进去
map.put(numbers[i],i);
}
}
return new int[]{-1,-1};
}
发表于 2023-05-23 14:01:14
回复(0)
import java.util.*;
public class Solution {
/**
* 不使用HashMap的一种方法，运行时间364ms,占用内存29140KB
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
int length = numbers.length;
int[] tool = Arrays.copyOf(numbers, length);
Arrays.sort(tool);
int[] result = new int[2];
for(int i=0,j=length-1;i<j;){
if(tool[i]+tool[j]<target){
i++;
}else if(tool[i]+tool[j]>target){
j--;
}else{
result[0]=tool[i];
result[1]=tool[j];
break;
}
}
int index1 = -1 ;
int index2 = -1 ;
for(int k=0;k<length;k++){
if(numbers[k] == result[0] && index1==-1){
index1=k;
}else if (numbers[k]==result[1] && index2==-1){
index2=k;
}
}
if(index1<index2){
result[0]=index1+1;
result[1]=index2+1;
}else {
result[0]=index2+1;
result[1]=index1+1;
}
return result;
}
}
发表于 2023-05-21 20:48:01
回复(0)
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
int[] res = new int[2];
if(numbers == null || numbers.length == 0){
return res;
}
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < numbers.length;i++){
int temp = target - numbers[i];
if(map.containsKey(temp)){
res[1] = i + 1;
res[0] = map.get(temp) + 1;
break;
}
map.put(numbers[i],i);
}
return res;
}
}
注意它示例里面下标从1开始
发表于 2023-03-27 11:42:11
回复(0)
两个相加不好都存到Map里面去，那么就使用减法来解决问题！！！
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;
}
}
发表于 2023-03-18 22:31:25
回复(1)
import java.util.*;
public class Solution {
private Map<Integer,Integer> map = new HashMap<>();
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
if (numbers == null || numbers.length <= 0) {
return new int[0];
}
for(int i = 0;i<numbers.length;i++) {
if(map.containsKey(target - numbers[i])) {
return new int[]{map.get(target - numbers[i]), i+1};
}else {
map.put(numbers[i], i+1);
}
}
return new int[0];
}
}
发表于 2023-03-09 06:55:14
回复(0)
import java.util.*;
public class Solution {
/**
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
int[] index = new int[2];
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < numbers.length; i++){
if(map.containsKey(target - numbers[i])){
index[0] = map.get(target - numbers[i]);
index[1] = i + 1;
}
map.put(numbers[i],i+1);
}
return index;
}
}
发表于 2022-12-06 17:38:06
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {
// write code here
for(int i=0; i< numbers.length;i++){
for(int j=i+1;j<numbers.length;j++){
if((numbers[i]+numbers[j])==target)
return new int[]{i+1,j+1};
}
}
return new int[2];
}
}
//运算没毛病，超时了
发表于 2022-10-31 14:24:14
回复(1)
问题信息
难度：
108条回答
1655收藏
82397浏览
通过挑战的用户
查看代码-
2023-03-14 18:42:07
-
2023-03-14 12:05:37
-
2023-03-13 11:14:56
-
2023-03-12 21:33:21 -
2023-03-12 11:11:39
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
