给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
这题有几种解法,其中一种比较优的解法是一次遍历+HashMap;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
另外,还有一种比较有趣的解法,如下,思路请见注释
public class Solution {
public int[] twoSum(int[] nums, int target) {
//100000000000
int volume =2048;
//011111111111
int bitMode = volume-1;
//生成一个足够的的数组,数组内的值默认为0
int [] result =new int[volume];
//循环传入的数组
for (int i=0;i<nums.length;i++){
//对计算后的值进行与运行,作用是获取它在新数组的下标值
//1.例如这题是target是9,传入的数组是{2, 7, 6, 11, 15, 5},第一个是2,(9-2)&bitmode = 7
//4.第2此循环,第2个值是7,(9-7)&bitmode = 2
int c = (target - nums[i]) & bitMode;
//因为默认数组内的值为0,如果为0即说明没有
//2.第一次循环时必定不进入
//5.第二此循环时,有上一次循环可知,此时result[2]=1,进入if内部
if (result[c]!=0){
//由于下面插入result数组时+1,这里要-1
//6.此时得出两数之和的下标
return new int[]{result[c]-1,i};
}
//因为if处判断条件为是否为0,所以此次的值必须+1,
//3.此时nums[0]=2,nums[i] & bitMode 为2,i=0,i+1=1,即result[2]=1
result[nums[i] & bitMode]=i+1;
}
return null;
}
public static void main(String[] args) {
int[] result = {2, 7, 6, 11, 15, 5};
int target = 9;
Solution s = new Solution();
int a[] = s.twoSum(result,target);
if (a!=null){
for (int oo:a) {
System.out.println(oo);
}
}
}
}
完~~