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

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

article 2024/11/18 20:28:27

两数之和

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)
            
          }//on
          for(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)
        
      }//on
      for(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};
}
}