当前位置：首页 > news >正文

两数之和三数之和哈希方法

news 2025/8/12 13:10:28

两数之和

package com;
import java.util.*;
public class Test5 {
//两数之和
public static void main(String[] args) {
int[] arr= {1,2,3,4,5,6,7,94,42,35};
int target=99;
Arrays.sort(arr);//快速排序
for(int i=0;i<arr.length;i++) {
int w=target-arr[i];
int index=Arrays.binarySearch(arr, w);//二分查找
if(index>=0) {
System.out.println(arr[i]+","+arr[index]);
break;
}
}
}
}

三数之和

package com;
import java.util.*;
public class Test5 {//两数之和哈希方法public static void main(String[] args) {int[] arr= {1,2,3,5,7,9,11,13,16,14,15,18,94,42,35};int target=40;HashMap<Integer,Integer> map=new HashMap<>();HashMap<Integer,Integer> map2=new HashMap<>();//去重for(int i=0;i<arr.length;i++) {map.put(arr[i],i);}for(int i=0;i<arr.length;i++) {int w=target-arr[i];int[] xx=get(arr,w,i);//两数之和//这个去重我没懂，但我觉得这个方法不够好，不好理解if(xx[0]!=-1){if(i!=xx[0]&&i!=xx[1]) {if(map2.get(i)==null||map2.get(xx[0])==null){map2.put(i,i);map2.put(xx[0],xx[0]);map2.put(xx[1],xx[1]);System.out.println(i+","+xx[0]+","+xx[1]);}}}}}public static int[] get(int[] arr,int target,int x) {HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<arr.length;i++) {map.put(arr[i],i);//存取o(1)}//onfor(int i=0;i<arr.length;i++) {int w=target-arr[i];Integer index=map.get(w);if(index!=null&&index!=i&&i!=x&&x!=index) {return new int[]{i,index};}}return new int[]{-1,-1};}
}

哈希方法

class Solution {public int[] twoSum(int[] nums, int target) {HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<nums.length;i++) {map.put(nums[i],i);//存取o(1)}//onfor(int i=0;i<nums.length;i++) {int w=target-nums[i];Integer index=map.get(w);if(index!=null&&index!=i) {return new int[]{i,index};}}return new int[]{0,0};
}
}