O(n) solution with explaination

  • 3
     * 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

    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.