describe

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].Copy the code

Train of thought

A for loop is used to determine the current number, and a nested for loop matches the second number, returning once the requirement is met.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] out = new int[2];
        for(int i =0; i<nums.length; i++){boolean flag = false;
            for(int j =i+1; j<nums.length; j++){if(nums[i] + nums[j] == target){
                    out[0] = i;
                    out[1] = j;
                    flag = true;
                    break; }}if(flag){
                break; }}returnout; }}Copy the code

Can be violent AC, but time and space complexity is not very good.

Given in the Java online submissions in each node.
Memory Usage: 39.3 MB, less than 6.43% of Java online submissions for Two Sum

To optimize the

You can see that map is used as an auxiliary query tool in the discussion area, which can greatly improve the speed of data retrieval.

public int[] twoSum(int[] numbers, int target) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(target - numbers[i])) {
            result[1] = i;
            result[0] = map.get(target - numbers[i]);
            return result;
        }
        map.put(numbers[i], i);
    }
    return result;
}Copy the code

The idea of the algorithm is as follows: the for loop is used to traverse, and the current data is the position recorded by I, but the difference is that it searches forward and matches the current data with the data that has been traversed before. In this way, the traversed data can be added to the map set, which facilitates comparison, saves retrieval time and rollback time, and avoids the problem of second match success.

Given in the Java online submissions with Two sums.
Memory Usage: 42.4 MB, less than 5.65% of Java online submissions for Two sums.

You can see a huge increase in time complexity and an increase in space expenditure.