Remove Elements

Description:

Given an array and a value, remove all instances of that > value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Solution 1. Brute Force

Time consuming... The idea is to go through the array twice, add each item up, and check the result with the target value, then return the indices.

• Time : O(n^2)

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

Solution 2. Hash Map

One idea is to use hashmap. Since hashmap stores data in a <key, value> form, we can scan the array and store the item and its index into the hash map first, then scan the array again, check if the key (target - nums[i]) is in the hashmap and return the index.

Note that we must check if the two indices are the same.

• Time：O(2n) = O(n)
• Space: O(n)

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

Solution 2'. Hash Map No. 2

The former solution requires to scan the array twice and check the indices. If a algorithm only scan the array once, there is no way that the indices confilt.

• Time: O(n)
• Space: O(n)

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