Question

Formatted question description: https://leetcode.ca/all/1.html


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

Algorithm

Generally speaking, in order to increase the complexity of time, you need to use space for exchange. This is considered a trade off.

But here I only want to use linear time complexity to solve the problem, that is, only one number can be traversed, then another number, you can store it in advance and use a HashMap to establish the mapping between the number and its coordinate position.

Since the HashMap is a constant-level search efficiency, when traversing the array, use the target to subtract the traversed number. It is another number you need, just look for it in the HashMap directly. Note that the number you find is not the first number. For example, if the target is 4 and a 2 is traversed, then the other 2 cannot be the previous one. 2.

The entire implementation steps are: first traverse the array once, establish a HashMap mapping, and then traverse again, start searching, and record the index when found.

Code

Java

import java.util.HashMap;

class Two_Sum {

    public static void main(String[] args) {

        Two_Sum out = new Two_Sum();
        Solution s = out.new Solution();

        int[] a = {2, 7, 11, 15};
        int target = 9;

        int[] result = s.twoSum(a, target);

        for (int each : result) {
            System.out.println(each);
        }
    }

    // time: O(N)
    // space: O(N)
    public class Solution {

        public int[] twoSum(int[] nums, int target) {

            // set up hashmap: remaining to original. thread-unsafe but for here is ok
            HashMap<Integer, Integer> hm = new HashMap<>();

            for (int i = 0; i < nums.length; i++) {

                // if key in hm, result found.
                // so that only one pass
                if (hm.containsKey(nums[i])) {
                    int otherIndex = hm.get(nums[i]);

                    return new int[]{Math.min(i, otherIndex) + 1, Math.max(i, otherIndex) + 1};
                }
                // put new record into hashmap
                else {
                    hm.put(target - nums[i], i);
                }
            }

            return null;
        }

    }
}

All Problems

All Solutions