您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

两数之和

第十三双眼睛2023-11-20【数据结构与算法】人已围观

简介两数之和
给定一个整数数组和一个整数目标值，请你在数组中找出何为目标值的那两个整数，并返回，你可以假设每种输入只会对应一种答案，但是数组中的同一个元素不能在数组中出现多次，可以按任意顺序返回答案

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

最简单的是暴力破解法，两层循环，第一层循环的时候，用目标值减去每个值，得出差值，第二轮循环中找这个差值，时间复杂度为O(n2)，代码如下：

public int[] twoSumMethod1(int[] nums, int target) {
int[] res = new int[2];
start:
for (int i = 0; i< nums.length; i++) {
int cha = target - nums[i];
for (int j = 0; j<nums.length; j++) {
if (nums[j] == cha && i != j) {
res[0] = i;
res[1] = j;
break start;
}
}
}
return res;
}

第二种方法：先循环一遍，因为数字不重复，所以，可以将数组封装称为一个map，第二轮循环的时候，用目标值减去每个值，得到差值，在数组中找是否存在差值。

public int[] twoSumMethod2(int[] nums, int target) {
   int[] res = new int[2];
   Map<Integer,Integer> map = new HashMap<>();
   for (int i = 0; i< nums.length; i++) {
       map.put(nums[i], i);
   }
   for (int j = 0; j< nums.length; j++) {
       int cha = target - nums[j];
       if (map.get(cha) != null && j != map.get(cha)) {
           res[0] = j;
           res[1] = map.get(cha);
           break;
       }
   }
   return res;
}

第三种方法：边循环，边用目标值减去当前值得到差值，在map里面寻找是否有该差值，如果有，则返回当前值和差值，如果没有，则将该值放入map，当前值为key，下标为value

public int[] twoSumMethod3(int[] nums, int target) {
   int[] res = new int[2];
   Map<Integer,Integer> map = new HashMap<>();
   for (int i = 0; i< nums.length; i++) {
       int cha = target - nums[i];
       if (map.containsKey(cha)) {
           res[0] = i;
           res[1] = map.get(cha);
       } else {
           map.put(nums[i], i);
       }
   }
   return res;
}

第一种是没有办法的办法，第二种比第一种好点，第三种是第一种和第二种的合体，是最好的。

Tags：

很赞哦！ ()

上一篇：马踏棋盘(图文)

下一篇：回文数(图文)