1. Two Sum (HashMap)

Brute Force

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

TC: $O(n^2)$

Remarks:

1. check the range of j: j will always be greater than i.
2. be careful of array index bound

Two-pass Hash Table

Check if the complement is in the array.

Steps:

1. create the hash table
2. find complmenet = target - num[i] in the hash table

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new Hashmap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containskey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }

        return new int[] { 0, 0 };
    }
}

Remarks:

1. containsKey with capital K
2. create java map

TC: $O(n)$

SC: $O(n)$

HashMap in Java

Insert key pairs: map.put(num1,num2)

Get a key: map.get(num)

Check if contain a key: map.containsKey(num)

Delete key: map.remove(key)

Get size: map.size()

Iterate: for (Map.Entry<K, V> entry : map.entrySet())

How Java did hashcode()?

By default, Object.hashCode() returns an integer derived from the object’s memory address (or a JVM-specific identity), potentially mixed to improve hash uniformity.

One-pass Hash Table

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

Remarks:

1. only put the value into the map after checking the key

TC: $O(n)$

SC: $O(n)$