每日一练.两数之和（Two Sum）

每日一练.两数之和（Two Sum）

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

法一：利用集合----HashMap

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class class01 {

public int[] twoSum(int[] nums, int target) {
int[] indexs = new int[2];

// 建立k-v ，一一对应的哈希表
HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
for(int i = 0; i < nums.length; i++){
if(hash.containsKey(nums[i])){
indexs[0] = hash.get(nums[i]);
indexs[1] = i;
return indexs;
}
// 将数据存入 key为补数 ，value为下标
hash.put(target-nums[i],i);
}
throw new IllegalArgumentException("No two sum solution");
}

public static void main(String[] args) {
//创建对象
class01 c = new class01();
//给定数组、目标
int[] nums = new int[]{2,5,7,11};
int target = 9;
//twoSum方法返回的是数组，所以要先存入变量answer
int[] answer= c.twoSum(nums, target);
//打印输出
System.out.println(Arrays.toString(answer));
}
}

法二：利用双重循环

public class class01 {

public int[] twoSum(int[] nums, int target) {

//创建数组，存储满足要求的数的下标
int[] indexs = new int[2];

// 双重循环 循环极限为(n^2-n)/2
for(int i = 0; i < nums.length; i++){
for(int j = nums.length - 1; j > i; j --){
if(nums[i]+nums[j] == target){
indexs[0] = i;
indexs[1] = j;
return indexs;
}
}
}
throw new IllegalArgumentException("No two sum solution");
}

public static void main(String[] args) {
//创建对象
class01 c = new class01();
//给定数组、目标
int[] nums = new int[]{2,5,7,11};
int target = 9;
//twoSum方法返回的是数组，所以要先存入变量answer
int[] answer= c.twoSum(nums, target);
//打印输出
System.out.println(Arrays.toString(answer));
}
}

法三：对于已排好序的，采用指针偏移

public class class01 {

public int[] twoSum(int[] nums, int target) {

int left = 0;
int right = nums.length-1;
int[] indexs = new int[]{left,right};

while(left<right){
int sum = nums[left] + nums[right];
if(sum<target){
left++;
}else if(sum>target){
right--;
}else{
indexs = new int[]{left,right};
return indexs;
}
}
return indexs;
}

public static void main(String[] args) {
//创建对象
class01 c = new class01();
//给定数组、目标
int[] nums = new int[]{2,5,7,11};
int target = 18;
//twoSum方法返回的是数组，所以要先存入变量answer
int[] answer= c.twoSum(nums, target);
//打印输出
System.out.println(Arrays.toString(answer));
}
}