Edward on Java with Leetcode: 1. Two Sum

Problem

Problem description is available at Two Sum.

Java Solution

The algorithm is pretty simple, use a hashmap to remember each visited number and its index in the form of “number:index”. When coming to a new number, mark it as x, and looking in the hashmap if y (equals to target-x) exists, if y is already in the hashmap, that means a previous visited y+x = target. Then basing on the requirement, the index of x and y should be returned.

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

        return null;
    }
}

Java Knowledge

I have learned or reminded myself (since I use Python more often) the below points:

1. Java variable needs a type and needs to end with “;”

Instead of “x=1”, I should write “int x=1;”.

2. Java use “null” to represent nothing rather than Python’s “None” .

3. Java’s hashmap is defined in java.util.HashMapas

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

That’s why the below line can compile (note that map is a Map while the “new” class is HashMap<>.

Map<Integer, Integer> map = new HashMap<>();

//below are also correct
Map<Integer, Integer> map = new HashMap();
Map<Integer, Integer> map = new HashMap<Integer, Integer>();

BTW, one should read the doc of java.util.HashMap, as it gives more insights of HashMap class. For example, it mentions HashMap is not thread safe:

Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

Map m = Collections.synchronizedMap(new HashMap(...));

4. Hashmap functions (not a complete list but a frequent one)

void put(K, V)

V get(K)

V remove(K)

int size()

boolean containsKey()

boolean containsValue()

Set<K> keySet()

5, Java Array

int[] a={}
a.length //represent an array's length, note "length" is not a function

This is a good introduction of Java array. Some key excerpts:

An array is an object of reference type which contains a fixed number of components of the same type; the length of an array is immutable. Creating an instance of an array requires knowledge of the length and component type. Each component may be a primitive type (such as byte, int, or double), a reference type (such as String, Object, or java.nio.CharBuffer), or an array. Multi-dimensional arrays are really just arrays which contain components of array type.

Arrays are implemented in the Java virtual machine. The only methods on arrays are those inherited from Object. The length of an array is not part of its type; arrays have a length field which is accessible via java.lang.reflect.Array.getLength().