O(n) solution with explaination


  • 3
    X
    /**
     * Create a new hash map to store the value and corresponding index in origin array
     * Search the result of target number minus current number in the hasp map
     * If another number is existed in hash map, return the index of two numbers
     * Otherwise, put current number as key and index as value to the hasp map
     * <p>
     * After traverse all array, then return null, means no such sum of two numbers in given array
     *
     * @param nums   a set of numbers
     * @param target sum value to be searched
     * @return index of two numbers
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> valueMap = new HashMap<>();
        for (int index = 0; index < nums.length; index++) {
            int anotherNum = target - nums[index];
            if (valueMap.containsKey(anotherNum)) {
                return new int[]{valueMap.get(anotherNum), index};
            }
            valueMap.put(nums[index], index);
        }
        return null;
    }
    

    reference: https://github.com/xinerd/algorithm/blob/master/LeetCode/src/cn/fmachine/leetcode/easy/TwoSum.java


  • 0
    P

    It's not o(n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.