[LeetCode Java Solution] Two Sum

Problem:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Method 1: O(n^2)

Use two for loop to check every combination.

Node that we need to put one return statement both inside and outside of the condition clause.

Code for method 1:

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

Method 2: O(n)

Use hash table. Key: the number that I am looking for. Value: the previous index.

Code for method 2:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        HashMap<Integer, Integer> dict = new HashMap<Integer, Integer>();
        dict.put (target-nums[0], 0);
        for (int i = 1; i < nums.length; i++){
            if (dict.containsKey(nums[i])){
                res[0] = dict.get(nums[i]) + 1;
                res[1] = i + 1;
                return res;
            }else{
                dict.put(target-nums[i],i);
            }
        }
        return res;
    }
}

Method 3: O(nlogn)

Use two pointer.

Be careful about finding the indexes after getting the right numbers.

Code for method 3:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        int low = 0;
        int high = nums.length - 1;
        
        int[] copy = new int[nums.length];
        System.arraycopy(nums,0, copy, 0,nums.length);
        Arrays.sort(copy);
        
        while( copy[low] + copy[high] != target ){
            if (copy[low] + copy[high] > target){
                high --;
            }else{
                low ++;
            }
        }
        
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == copy[low] || nums[i] == copy[high]){
                if (res[0] == 0){
                    res[0] = i+1;
                }else{
                    res[1] = i+1;
                }
            }
        }
        
        Arrays.sort(res);
        
        return res;
    }
}

[LeetCode java solution] – String/Hashtable – Anagrams

Problem:

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Method:

Create a HashMap:

key: String (after chars are sorted);

value: The specific corresponding string.

Then, iterate through the HashMap. If there is a key with more than two values, we add them into the result container.

Code:

public class Solution {
    public ArrayList<String> anagrams(String[] strs) {
        if (strs == null || strs.length == 0) return null;
        ArrayList<String> res = new ArrayList<String>();
        
        HashMap<String, ArrayList<String>> dict = new HashMap<String, ArrayList<String>>();
        
        for (int i = 0; i < strs.length; i++){
            char[] c = strs[i].toCharArray();
            Arrays.sort(c);
            String s = new String(c);
            if (dict.containsKey(s)){
                dict.get(s).add(strs[i]);
            }else{
                ArrayList<String> l = new ArrayList<String>();
                l.add(strs[i]);
                dict.put(s,l);
            }
        }
        Iterator iter = dict.values().iterator();
        while(iter.hasNext()){
            ArrayList<String> temp = (ArrayList<String>)iter.next();  //cast type!!
            if(temp.size() > 1){
              res.addAll(temp);
            }
        }
        return res;
    }
}