pros: add, delete, find O(1) time
cons: much storage O(n) space
key value -> int num(in hash function) -> num % n as index

using array, list, resize

When the data is 90% full in the table or more, the efficience begins to drop.
avoid conflict: Linked List in Arrays
if data/size.array() || length.LinkedList > 5:
resize: 2 times size of the array

HashSet & HashMap

• find the ith elements from a data set [array]
• data are sorted(find max/min [heap], find a element greater than a given number [BST])
• hash table find strings with a prefix

replaced by array

• If the number of keys is fixed and not large, use the array.
• Array’s find function is quicker than hash table.
  create
  

  1 2	Map<key type, value type> map = new HashMap<>(); || HashMap<key type, value type> map = new HashMap<>();

possible solution1

1

Arrays.sort(array)  // sort the array in ascii

O(nlogn) time
hash table/array
int[] counts = new int[26];

like “dictionary” Map<String, List>

• insert delete: hash table
• get random: array O(1), linkedlist O(n)
• Random type
  

  1 2	Random random = new Random(); random.nextInt(int n); //create a random integer from [0,n)

Solution

1
2

HashMap<Integer, Integer> numToLocation;
ArrayList<Integer> nums;

first integer -> value, second integer -> index

Think about how and when to move the 2 pointers.

• brute force
  all permutations of s1
  each ? substring of s2
• optimization
  using 2 pointers to get a s1-length substring of s2
  hash table anagram s1, sub_s2(left++,right–)
  O(n) time, O(1) space
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  int[] counts = new int[26]; if (s1.length()<s2.length()) { //Begin with first window for (int i = 0; i < s1.length(); i++) { counts[s1.chatAt(i)-'a']++; counts[s2.charAt(i)-'a']--; } //determine whether it's an anagram if (areAllZero(counts)) return true; //滑动窗口，右指针从s1.length()开始，左指针为右-s1.length() for (int i = s1.length(); i<s2.length(); i++) { //right pointer char--，left pointer char++ counts[s2.charAt(i)-'a']--; counts[s2.charAt(i)-s1.length()-'a']++; if (areAllZero(counts)) return true; } return false; }

• As above.
• Use a list to record the indices.

• if key’s value > 1, it’s repeating
• determine: how and when do the pointers move
  right: include more character (not repeated)
  left: exclude some character (repeated)
  right begins from 0, left begins from -1
  if the subject doesn’t say the letters are lowercases, use ASCII and the array’s length should be [256].
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  int[] counts = new int[256]; int longest = s.length() > 0 ? 1:0; for (int i=0, j=-1; i<s.length(); i++) { counts[s.charAt(i)]++; //make it without repeating while (GreaterThan1(counts)) { j++; counts[s.charAt(j)]--; } //2 situations: not longer or longer longest = Math.max(i-j, longest); } return longest;

• optimization: replace GreaterThan1() with a 2-time-exist index
  it has to scan 256’s room every time use GreaterThan1()
  

  1 2 3 4 5 6 7 8 9 10 11

  int countDup = 0; ... if (counts[s.charAt(i)] == 2) countDup++; while (countDup>0) { j++; counts[s.charAt(j)]--; //make sure the str is with no repeating if (s.charAt(j) == 1) countDup--; } longest = Math.max(...)

• int minLen = Integer.MAX_VALUE; (2^32-1)
• str.substring(a,b) get a substring of str from index=a to index = b-1
  e.g. str=abcdefg;
  str.substring(4,6) = ef
• a++: a doesn’t change until this line finishes.
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

  //record the length of t, and use countToMatch to see //whether it's matched while the hash table records the exist times. int countToMatch = t.length(), left = 0, right = 0; int head = 0, minLen = Integer.MAX_VALUE; while (right<s.length()) { if (counts[s.charAt(right++)]-- > 0) { countToMatch--; } while (countToMatch == 0) { if (right-left < minLen) { head = left; minLen = right - left; } //if the character exists in t, the value should be 0; //or it should be < 0; if (counts[s.charAt(left++)]++ == 0) { countToMatch++; } } return minLen == Integer.MAX_VALUE ? "" : s.substring(head,head+minLen); }