Hashtable hash table and index 1, 599, 219

219. There are duplicate elements II

Given an array of integers and an integer k, Determine if there are two different indexes in the array i and j, bring nums [i] = nums [j], also i and j The absolute value of the difference of is at most k

Example 1:
Input : nums = [1,2,3,1], k = 3
Output : true
Example 2:
Input : nums = [1,0,1,1], k = 1
Output : true
Example 3:
Input : nums = [1,2,3,1,2,3], k = 2
Output : false
Answer key ：
1）hash Traverse once , When duplicate numbers appear, judge whether the conditions are met and update map
sloution：

class Solution {
    
    public boolean containsNearbyDuplicate(int[] nums, int k) {
    
    Map<Integer,Integer> map=new HashMap<>();
    int n=0;
    for(int j=0;j<nums.length;j++){
    
        if(map.containsKey(nums[j]) && Math.abs(j-map.get(nums[j]))<=k)  return true;   
        map.put(nums[j],j);
     }
        return false;
    }
}

599. The minimum index sum of two lists

hypothesis Andy and Doris Want to choose a restaurant for dinner , And they all have a list of their favorite restaurants , The name of each restaurant is represented by a string .
You need to help them use the least index and find their favorite restaurants . If there is more than one answer , Then all the answers are output regardless of the order . You can assume that there is always an answer .

Example 1:
Input :
[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
Output : [“Shogun”]
explain : Their only favorite restaurant is “Shogun”.

Example 2:
Input :
[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[“KFC”, “Shogun”, “Burger King”]
Output : [“Shogun”]
explain : Their favorite restaurant with the smallest index and is “Shogun”, It has the smallest index and 1(0+1).

Tips :
The length range of both lists is [1, 1000] Inside .
The length of the strings in the two lists will be in [1,30] Within the scope of .
Subscript from 0 Start , Reduce the length of the list by 1.
Neither list has duplicate elements .
Answer key ：
1） use map preservation list1 The name and serial number of the restaurant in , use list2 Chinese restaurant name to match list1 Medium hashmap, If the match is successful, the sequence and ; 1. If the sum of serial numbers is less than the current minimum sum, Empty result array , Deposit new restaurant name ; 2. If the sum of serial numbers is equal to the current minimum , Store the result in the current restaurant name array ; Last returned result array

sloution：

class Solution {
    
    public String[] findRestaurant(String[] list1, String[] list2) {
    
    Map<String,Integer> map=new HashMap<>();
    for(int i=0;i<list1.length;i++){
    
         map.put(list1[i],i);
    }

    List<String> list=new ArrayList();
    int sum=Integer.MAX_VALUE;
    for(int j=0;j<list2.length;j++){
    
        int n=Integer.MAX_VALUE;
        if(map.containsKey(list2[j]))  n=j+map.get(list2[j]);
        else continue;
        if(n>sum) continue;
        else if(n==sum) list.add(list2[j]);
        else{
    
            sum=n;
            list.clear();
            list.add(list2[j]);
        }
    }
    return list.toArray(new String[list.size()]);
    }
}

1. Sum of two numbers

Given an array of integers nums And a target value target, Please find and as the target value in the array Two Integers , And return their array subscripts .
You can assume that each input corresponds to only one answer . however , The same element in an array cannot be used twice .

Example :
Given nums = [2, 7, 11, 15], target = 9
because nums[0] + nums[1] = 2 + 7 = 9
So back [0, 1]
Answer key ：
1） violence Double cycle
2）hash
sloution：

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
      Map<Integer, Integer> map = new HashMap<>();
      for(int i = 0; i< nums.length; i++) {
    
            if(map.containsKey(target - nums[i])) {
    
                return new int[] {
    map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
      }  
       throw new IllegalArgumentException("No two sum solution");
    }
}