给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
数据范围：%20%5Cleq%2010%5E5)
，
，
要求：空间复杂度 )
，时间复杂度 )
[编程题]两数之和
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)
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[] r = new int[2];
int j = 0;
Map map = new HashMap<>();
for (int i = 0; i < numbers.length; i++) {
if (!map.containsKey(target - numbers[i])) {
map.put(numbers[i], i + 1);
} else {
r[j++] = (int)map.get(target - numbers[i]);
r[j] = i + 1;
}
}
Arrays.sort(r);
return r;
}
}
发表于 2022-09-18 17:10:17
回复(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[] result=new int[2];
for(int i=1;i<=numbers.length-1;i++){
for(int j=i+1;j<=numbers.length;j++){
if(numbers[i-1]+numbers[j-1]==target){
result[0]=i;
result[1]=j;
break;
}
}
}
return result;
}
}
发表于 2022-08-02 16:22:52
回复(2)
效率很低，思路简单
public int[] twoSum (int[] numbers, int target) {
// write code here
// write code here
if(numbers.length==0) return new int[0];
//用一个二维数据保存原数组的值和索引 例如 原数组 [0,4,3,0]] 新数组[[0,0],[4,1],[3,2],[0,3]]
int[][] aa = new int[numbers.length][0];
for (int i = 0; i <numbers.length ; i++) {
aa[i]=new int[]{numbers[i],i};
}
//排序新数组 用于二分查找
Arrays.sort(aa, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
int[][] aa = new int[numbers.length][0];
for (int i = 0; i <numbers.length ; i++) {
aa[i]=new int[]{numbers[i],i};
}
//排序新数组 用于二分查找
Arrays.sort(aa, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
//二分查找
int low=0;
int high=numbers.length-1;
while(low<=high){
if (aa[low][0]+aa[high][0]==target) {
int[] ints1 = new int[2];
int low=0;
int high=numbers.length-1;
while(low<=high){
if (aa[low][0]+aa[high][0]==target) {
int[] ints1 = new int[2];
//索引记得+1
ints1[0]=aa[low][1]+1;
ints1[1]=aa[high][1]+1;
Arrays.sort(ints1
);
return ints1;
} else if (aa[low][0]+aa[high][0]>target) {
high--;
} else if (aa[low][0]+aa[high][0]<target) {
low++;
}
}
return null;
}
ints1[0]=aa[low][1]+1;
ints1[1]=aa[high][1]+1;
Arrays.sort(ints1
);
return ints1;
} else if (aa[low][0]+aa[high][0]>target) {
high--;
} else if (aa[low][0]+aa[high][0]<target) {
low++;
}
}
return null;
}
发表于 2022-07-16 10:34:39
回复(0)
int[] ints = new int[2]; Map<Integer,Integer> map = new HashMap(); for (int i = 0; i < numbers.length; i++) { Integer nn = numbers[i]; //第一次判断差值里是否有该值 if (map.containsKey(nn)) { ints[0] = map.get(nn) + 1; ints[1] = i + 1; return ints; } int cha = target - nn; map.put(cha,i);}用Map就能过，用list装就超时
发表于 2022-06-14 17:07:23
回复(0)
问题信息
难度：
104条回答
1515收藏
78118浏览
通过挑战的用户
-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
