两数之和---哈希表一.分析二.解题三.答案三.知识扩充---哈希表

71 阅读 0 评论 47 点赞

我是靠谱客的博主沉默鸵鸟，最近开发中收集的这篇文章主要介绍两数之和---哈希表一.分析二.解题三.答案三.知识扩充---哈希表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一.分析

1.题设中提到，假设只有一组答案，所以当找到符合题设的组合时，循环结束，不需要考虑其他组合则依次将数组中每个值，与后面的值视为组合讨论即可。

2.定义方法定义成数组类型

二.解题

暴力法

package 两数之和;
import java.util.Scanner;
public class demo {
public static int[] select(int []nums,int target){
int []result=new int[2];
for (int i=0;i<nums.length-1;i++){
for (int j=i+1;j<nums.length;j++){
int sum=nums[i]+nums[j];
if (sum==target){
result[0]=i;
result[1]=j;
return result;
}
}
}
return result;
}
public static void main(String[] args) {
Scanner a=new Scanner(System.in);
int target= a.nextInt();
int []nums=new int[4];
for (int i=0;i<4;i++){
nums[i]=a.nextInt();
}
int[] result=select(nums,target);
for (int i=0;i<result.length;i++){
System.out.println(result[i]);
}
}
}

1. int[] result=select(nums,target);

以此方法接受返回的数组

三.答案

1.暴力法

class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}

1.1return new int[]{i, j};

返回的数组，使用静态方法定义

1.2 return new int[0];

由题意可知题中有且只有一解所以根本不可能进行到这一行返回空数组即可

2.优化

class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}

三.知识扩充---哈希表

转载：链接

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表，哈希表其实是一种数据结构。

哈希表中是通过哈希函数将一个值映射到另外一个值的，所以在哈希表中，a映射到b，a就叫做键值，而b呢？就叫做a的哈希值，也就是hash值。