Topic describes

Given an integer array nums and an integer target value target, find the two integers in the array and the target values and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer.

You can return the answers in any order.

Example 1: input: nums = [2,7,11,15], target = 9 output: [0,1] description: because nums[0] + nums[1] == 9, return [0,1]. Example 2: input: nums = [3,2,4], target = 6 output: [1,2] example 3: input: nums = [3,3], target = 6 output: [0,1]Copy the code

Thought analysis

The O(n^2) idea is easy and I won’t go over it here. So let’s do it in order n. In order to do O(n), we have to be able to remember which numbers we walked through before. We can use the map structure to record. The key of the map is the value traversed, and the value is the index of the value. So when we iterate over a value val, we need to see if target-val exists in the map. Take its subscript if it exists.

AC code

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